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.



Complexity of determining if two graphs have same cycle matroid?
The following paper seems to show that this problem is polynomial equivalent to graph isomorphism (see section 5):


<http://arxiv.org/abs/0811.3859>


