show/hide this revision's text 2 edited tags
show/hide this revision's text 1

Complexity of determining if two graphs have same cycle matroid?

Consider the following question:

Input: Two graphs G1 and G2

Question: Is the cycle matroid M(G1) isomorphic to the cycle matroid M(G2)

What is the complexity of this question?

It is well known that the two cycle matroids are isomorphic if and only if the graphs are "2-isomorphic" which means that there is a sequence of "Whitney flips" (where a graph is disconnected at a 2-vertex cutset and then reconnected with one of the pieces flipped) from one to an isomorph of the other.

This suggests that the complexity should be the same as graph isomorphism, but I cannot find a reference to this.