On the Complexity of Matroid Isomorphism Problem

Details On the Complexity of Matroid Isomorphism Problem On the Complexity of Matroid Isomorphism Problem

2008-11-24

arxiv.org/abs/0811.3859v1

Computer Science

Computational Complexity

Scientific paper

We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in $\Sigma_2^p$. In the case of linear matroids, which are represented over polynomially growing fields, we note that the problem is unlikely to be $\Sigma_2^p$-complete and is $\co\NP$-hard. We show that when the rank of the matroid is bounded by a constant, linear matroid isomorphism, and matroid isomorphism are both polynomial time many-one equivalent to graph isomorphism. We give a polynomial time Turing reduction from graphic matroid isomorphism problem to the graph isomorphism problem. Using this, we are able to show that graphic matroid isomorphism testing for planar graphs can be done in deterministic polynomial time. We then give a polynomial time many-one reduction from bounded rank matroid isomorphism problem to graphic matroid isomorphism, thus showing that all the above problems are polynomial time equivalent. Further, for linear and graphic matroids, we prove that the automorphism problem is polynomial time equivalent to the corresponding isomorphism problems. In addition, we give a polynomial time membership test algorithm for the automorphism group of a graphic matroid.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Matroid Isomorphism Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of Matroid Isomorphism Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Matroid Isomorphism Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-645074