On the complexity of matroid isomorphism problem

DOI10.1007/S00224-010-9260-0MaRDI QIDQ639843zbMATH OpenOpenAlexFDO

Authors B. V. Raghavendra Rao, Jayalal Sarma M. N.

Publication date 11 October 2011

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0811.3859

zbMATH Keywords

computational complexitymatroid isomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in $Sigm{a}_2^p$. In the case of linear matroids, which are represented over polynomially growing fields, we note that the problem is unlikely to be $Sigm{a}_2^p$-complete and is $coNP$-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.

Recommendations

• On the Complexity of Matroid Isomorphism Problems
• Complexity of testing reachability in matroids
• Determining when a graphic matroid is transversal in linear time
• The complexity of the matroid homomorphism problem
• On Matroid Representability and Minor Problems

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 5605063 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 6146491 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• 3-connected Planar Graph Isomorphism is in Log-space
• A Combinatorial Decomposition Theory
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Chromatic, Flow and Reliability Polynomials: The Complexity of their Coefficients
• Computational Complexity
• Dividing a Graph into Triconnected Components
• Graph Isomorphism is in SPP
• Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Matroid Complexity and Nonsuccinct Descriptions
• On Whitney's 2‐isomorphism theorem for graphs
• On the Abstract Properties of Linear Dependence
• Probabilistic complexity classes and lowness
• Some hard problems on matroid spikes
• Vector representable matroids of given rank with given automorphism group

Cited in

(9)

• On the Complexity of Some Enumeration Problems for Matroids
• On the complexity of polytope isomorphism problems
• The complexity of the matroid homomorphism problem
• Matroid Complexity and Nonsuccinct Descriptions
• Testing mutual duality of planar graphs
• On the Complexity of Matroid Isomorphism Problems
• Isomorphism testing of read-once functions and polynomials
• Complexity of testing reachability in matroids
• Determining when a graphic matroid is transversal in linear time

This page was built for publication: On the complexity of matroid isomorphism problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q639843)