Return to Answer

I believe that they have the same complexity, but writing up the details has proved painful and it is possible I am missing something. Let me give the first part of my answer, and see whether you actually want more.

A graph is called 3-connected if it cannot be disconnected by removing two vertices. If G and H are 3-connected then they are isomorphic if and only if their matroids are isomorphic. (Follows immediately from Whitney's theorem, as there are no Whitney moves on 3-connected graphs.) So this subproblem of graph isomorphism and this subproblem of graphical matroid isomorphism are equivalent.

Now, it is easy to reduce graph isomorphism to 3-connected graph isomorphism. If G is any graph, let J_3(G) be the graph formed from G by adding 3 more vertices which are joined to each other and to every vertex of G. Then J_3(G) is isomorphic to J_3(H) if and only if G is isomorphic to H.

So [Graph isomorphism], [3-connected graph isomorphism] and [3-connected graphical matroid isomorphism] are equivalent, and [graphical matroid isomorphism] is at least as hard as these.

The part which is truly painful to write up is the reduction of graphical matroid isomorphism to 3-connected graphical matroid isomorpism. (And maybe I am missing something.) Here's how it should go. We can immediately reduce to the case of 2-connected graphs, because the matroid of a graph is determined by the matroids of its 2-connected components.

The next step is to break the graph into its representation as a 2-sum of 3-connected components. This is a less standard notion, so I'll sketch the idea. Some details are slightly wrong (mostly having to do with multiple edges); see the reference I link for full details. Let G be a 2-connected graph. If G is 3-connected, then it is its own 2-sum representation. If not, let G - {u,v} decompose as C_1 \cup C_2 \cup ... \cup C_r. Take C_i and add two vertices u_i and v_i. There is an edge from u_i to each vertex of C_i which was joined to u, and similarly for v. Also, there is an edge from u_i to v_i. Call this modified graph G_i. If G_i is 3-connected, stop. If not, break it up in a similar manner. Keep proceeding in this way until we have a multiset of 3-connected graphs. It is not hard to see that, even implemented stupidly, this is a polynomial process.

A theorem of Cunningham and Edmonds states that this multiset is an isomorphism invariant of the matroid of G. Moreover, Cunningham and Edmonds also work out all the different ways to put these graphs together to obtain isomorphic graphical matroids. (One of their rules is the Whitney flip, which corresponds to gluing G_1 and G_2 together with u_2 and v_2 switched.) It shouldn't be too hard to see that their rule is effectively computable, but its giving me some trouble, so I'll stop here.

I believe that they have the same complexity, but writing up the details has proved painful and it is possible I am missing something. Let me give the first part of my answer, and see whether you actually want more.

A graph is called 3-connected if it cannot be disconnected by removing two vertices. If G and H are 3-connected then they are isomorphic if and only if their matroids are isomorphic. (Follows immediately from Whitney's theorem, as there are no Whitney moves on 3-connected graphs.) So this subproblem of graph isomorphism and this subproblem of graphical matroid isomorphism are equivalent.

Now, it is easy to reduce graph isomorphism to 3-connected graph isomorphism. If G is any graph, let J_3(G) be the graph formed from G by adding 3 more vertices which are joined to each other and to every vertex of G. Then J_3(G) is isomorphic to J_3(H) if and only if G is isomorphic to H.

So [Graph isomorphism], [3-connected graph isomorphism] and [3-connected graphical matroid isomorphism] are equivalent, and [graphical matroid isomorphism] is at least as hard as these.

The part which is truly painful to write up is the reduction of graphical matroid isomorphism to 3-connected graphical matroid isomorpism. (And maybe I am missing something.) Here's how it should go. We can immediately reduce to the case of 2-connected graphs, because the matroid of a graph is determined by the matroids of its 2-connected components.

The next step is to break the graph into its representation as a 2-sum of 3-connected components. This is a less standard notion, so I'll sketch the idea. Some details are slightly wrong (mostly having to do with multiple edges); see the reference I link for full details. Let G be a 2-connected graph. If G is 3-connected, then it is its own 2-sum representation. If not, let G - {u,v} decompose as C_1 \cup C_2 \cup ... \cup C_r. Take C_i and add two vertices u_i and v_i. There is an edge from u_i to each vertex of C_i which was joined to u, and similarly for v. Also, there is an edge from u_i to v_i. Call this modified graph G_i. If G_i is 3-connected, stop. If not, break it up in a similar manner. Keep proceeding in this way until we have a multiset of 3-connected graphs. It is not hard to see that, even implemented stupidly, this is a polynomial process.

A theorem of Cunningham and Edmonds states that this multiset is an isomorphism invariant of the matroid of G. Moreover, Cunningham and Edmonds also work out all the different ways to put these graphs together to obtain isomorphic graphical matroids. (One of their rules is the Whitney flip, which corresponds to gluing G_1 and G_2 together with u_2 and v_2 switched.) It shouldn't be too hard to see that their rule is effectively computable, but its giving me some trouble, so I'll stop here. ADDED: I'll say that I have worked with the Cunningham/Edmonds rule in hand computations and never had any trouble checking it; I'm just having trouble with formally showing it is efficiently checkable.

I believe that they have the same complexity, but writing up the details has proved painful and it is possible I am missing something. Let me give the first part of my answer, and see whether you actually want more.

A graph is called 3-connected if it cannot be disconnected by removing two vertices. If G and H are 3-connected then they are isomorphic if and only if their matroids are isomorphic. (Follows immediately from Whitney's theorem, as there are no Whitney moves on 3-connected graphs.) So this subproblem of graph isomorphism and this subproblem of graphical matroid isomorphism are equivalent.

Now, it is easy to reduce graph isomorphism to 3-connected graph isomorphism. If G is any graph, let J_3(G) be the graph formed from G by adding 3 more vertices which are joined to each other and to every vertex of G. Then J_3(G) is isomorphic to J_3(H) if and only if G is isomorphic to H.

So [Graph isomorphism], [3-connected graph isomorphism] and [3-connected graphical matroid isomorphism] are equivalent, and [graphical matroid isomorphism] is at least as hard as these.

The part which is truly painful to write up is the reduction of graphical matroid isomorphism to 3-connected graphical matroid isomorpism. (And maybe I am missing something.) Here's how it should go. We can immediately reduce to the case of 2-connected graphs, because the matroid of a graph is determined by the matroids of its 2-connected components.

The next step is to break the graph into its representation as a 2-sum of 3-connected components. This is a less standard notion, so I'll sketch the idea. Some details are slightly wrong (mostly having to do with multiple edges); see the reference I link for full details. Let G be a 2-connected graph. If G is 3-connected, then it is its own 2-sum representation. If not, let G - {u,v} decompose as C_1 \cup C_2 \cup ... \cup C_r. Take C_i and add two vertices u_i and v_i. There is an edge from u_i to each vertex of C_i which was joined to u, and similarly for v. Also, there is an edge from u_i to v_i. Call this modified graph G_i. If G_i is 3-connected, stop. If not, break it up in a similar manner. Keep proceeding in this way until we have a multiset of 3-connected graphs. It is not hard to see that, evenly implemented stupidly, this is a polynomial process.

A theorem of Cunningham and Edmonds states that this multiset is an isomorphism invariant of the matroid of G. Moreover, Cunningham and Edmonds also work out all the different ways to put these graphs together to obtain isomorphic graphical matroids. (One of their rules is the Whitney flip, which corresponds to gluing G'_1 and G'_2 together with u' and v' switched in one of the two pieces.) It shouldn't be too hard to see that their rule is effectively computable, but its giving me some trouble, so I'll stop here.

I believe that they have the same complexity, but writing up the details has proved painful and it is possible I am missing something. Let me give the first part of my answer, and see whether you actually want more.

A graph is called 3-connected if it cannot be disconnected by removing two vertices. If G and H are 3-connected then they are isomorphic if and only if their matroids are isomorphic. (Follows immediately from Whitney's theorem, as there are no Whitney moves on 3-connected graphs.) So this subproblem of graph isomorphism and this subproblem of graphical matroid isomorphism are equivalent.

Now, it is easy to reduce graph isomorphism to 3-connected graph isomorphism. If G is any graph, let J_3(G) be the graph formed from G by adding 3 more vertices which are joined to each other and to every vertex of G. Then J_3(G) is isomorphic to J_3(H) if and only if G is isomorphic to H.

So [Graph isomorphism], [3-connected graph isomorphism] and [3-connected graphical matroid isomorphism] are equivalent, and [graphical matroid isomorphism] is at least as hard as these.

The part which is truly painful to write up is the reduction of graphical matroid isomorphism to 3-connected graphical matroid isomorpism. (And maybe I am missing something.) Here's how it should go. We can immediately reduce to the case of 2-connected graphs, because the matroid of a graph is determined by the matroids of its 2-connected components.

The next step is to break the graph into its representation as a 2-sum of 3-connected components. This is a less standard notion, so I'll sketch the idea. Some details are slightly wrong (mostly having to do with multiple edges); see the reference I link for full details. Let G be a 2-connected graph. If G is 3-connected, then it is its own 2-sum representation. If not, let G - {u,v} decompose as C_1 \cup C_2 \cup ... \cup C_r. Take C_i and add two vertices u_i and v_i. There is an edge from u_i to each vertex of C_i which was joined to u, and similarly for v. Also, there is an edge from u_i to v_i. Call this modified graph G_i. If G_i is 3-connected, stop. If not, break it up in a similar manner. Keep proceeding in this way until we have a multiset of 3-connected graphs. It is not hard to see that, even implemented stupidly, this is a polynomial process.

A theorem of Cunningham and Edmonds states that this multiset is an isomorphism invariant of the matroid of G. Moreover, Cunningham and Edmonds also work out all the different ways to put these graphs together to obtain isomorphic graphical matroids. (One of their rules is the Whitney flip, which corresponds to gluing G_1 and G_2 together with u_2 and v_2 switched.) It shouldn't be too hard to see that their rule is effectively computable, but its giving me some trouble, so I'll stop here.

I believe that they have the same complexity, but writing up the details has proved painful and it is possible I am missing something. Let me give the first part of my answer, and see whether you actually want more.

A graph is called 3-connected if it cannot be disconnected by removing two vertices. If G and H are 3-connected then they are isomorphic if and only if their matroids are isomorphic. (Follows immediately from Whitney's theorem, as there are no Whitney moves on 3-connected graphs.) So this subproblem of graph isomorphism and this subproblem of graphical matroid isomorphism are equivalent.

Now, it is easy to reduce graph isomorphism to 3-connected graph isomorphism. If G is any graph, let J_3(G) be the graph formed from G by adding 3 more vertices which are joined to each other and to every vertex of G. Then J_3(G) is isomorphic to J_3(H) if and only if G is isomorphic to H.

So [Graph isomorphism], [3-connected graph isomorphism] and [3-connected graphical matroid isomorphsim] are equivalent, and [graphical matroid isomorphism] is at least as hard as these.

The part which is truly painful to write up is the reduction of graphical matroid isomorphism to 3-connected graphical matroid isomorpism. (And maybe I am missing something.) Here's how it should go. We can immediately reduce to the case of 2-connected graphs, because the matroid of a graph is determined by the matroids of its 2-connected components.

The next step is to break the graph into its representation as a 2-sum of 3-connected components. This is a less standard notion, so I'll sketch the idea. Let G be a 2-connected graph. If it is 3-connected, then G is its own 2-sum representation. If not, choose {u,v} such that G - {u,v} is disconnected, and let G_1, G_2, ..., G_r be the connected components of G - {u,v}. Let G'_i be the graph formed from G_i by adding two vertices u' and v', joined by an edge, where u is attached to the vertices of G_i that used to be attached to u and similarly for v' and the vertices that used to be attached to v. Now repeat this process with each G'_i and keep going until we obtain a multiset of 3-connected graphs. It is not hard to see that this process stops in polynomial time.

A theorem of Cunningham and Edmonds states that the final multiset of connected graphs is an isomorphism invariant of the matroid of G. Moreover, Cunningham and Edmonds also work out all the different ways to put these graphs together to obtain isomorphic graphical matroids. (One of their rules is the Whitney flip, which corresponds to gluing G'_1 and G'_2 together with u' and v' switched in one of the two pieces.) It shouldn't be too hard to see that their rule is effectively computable, but its giving me some trouble, so I'll stop here.

I believe that they have the same complexity, but writing up the details has proved painful and it is possible I am missing something. Let me give the first part of my answer, and see whether you actually want more.

A graph is called 3-connected if it cannot be disconnected by removing two vertices. If G and H are 3-connected then they are isomorphic if and only if their matroids are isomorphic. (Follows immediately from Whitney's theorem, as there are no Whitney moves on 3-connected graphs.) So this subproblem of graph isomorphism and this subproblem of graphical matroid isomorphism are equivalent.

Now, it is easy to reduce graph isomorphism to 3-connected graph isomorphism. If G is any graph, let J_3(G) be the graph formed from G by adding 3 more vertices which are joined to each other and to every vertex of G. Then J_3(G) is isomorphic to J_3(H) if and only if G is isomorphic to H.

So [Graph isomorphism], [3-connected graph isomorphism] and [3-connected graphical matroid isomorphism] are equivalent, and [graphical matroid isomorphism] is at least as hard as these.

The part which is truly painful to write up is the reduction of graphical matroid isomorphism to 3-connected graphical matroid isomorpism. (And maybe I am missing something.) Here's how it should go. We can immediately reduce to the case of 2-connected graphs, because the matroid of a graph is determined by the matroids of its 2-connected components.

The next step is to break the graph into its representation as a 2-sum of 3-connected components. This is a less standard notion, so I'll sketch the idea. Some details are slightly wrong (mostly having to do with multiple edges); see the reference I link for full details. Let G be a 2-connected graph. If G is 3-connected, then it is its own 2-sum representation. If not, let G - {u,v} decompose as C_1 \cup C_2 \cup ... \cup C_r. Take C_i and add two vertices u_i and v_i. There is an edge from u_i to each vertex of C_i which was joined to u, and similarly for v. Also, there is an edge from u_i to v_i. Call this modified graph G_i. If G_i is 3-connected, stop. If not, break it up in a similar manner. Keep proceeding in this way until we have a multiset of 3-connected graphs. It is not hard to see that, evenly implemented stupidly, this is a polynomial process.

A theorem of Cunningham and Edmonds states that this multiset is an isomorphism invariant of the matroid of G. Moreover, Cunningham and Edmonds also work out all the different ways to put these graphs together to obtain isomorphic graphical matroids. (One of their rules is the Whitney flip, which corresponds to gluing G'_1 and G'_2 together with u' and v' switched in one of the two pieces.) It shouldn't be too hard to see that their rule is effectively computable, but its giving me some trouble, so I'll stop here.