The complexity of the matroid homomorphism problem

DOI10.37236/11119MaRDI QIDQ6162136zbMATH OpenFDO

Authors Cheolwon Heo, Hyobin Kim, Siggers Mark

Publication date 15 June 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/11119

zbMATH Keywords

binary matroidmatroid homomorphism

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Analysis of algorithms and problem complexity (68Q25)

Review text

Summary: We show that for every binary matroid \(N\) there is a graph \(D(N)\) such that for the graphic matroid \(M_G\) of a graph \(G\), there is a matroid-homomorphism from \(M_G\) to \(N\) if and only if there is a graph-homomorphism from \(G\) to \(D(N)\). With this we prove a complexity dichotomy for the problem \(\mathrm{Hom}_{\mathbb{M}}(N)\) of deciding if a binary matroid \(M\) admits a homomorphism to \(N\). The problem is polynomial time solvable if \(N\) has a loop or has no circuits of odd length, and is otherwise NP-complete. We also get dichotomies for the list, extension, and retraction versions of the problem.

Recommendations

• A note on maxflow-mincut and homomorphic equivalence in matroids
• Complexity of tree homomorphisms
• On the complexity of matroid isomorphism problem
• On the Complexity of Matroid Isomorphism Problems
• scientific article; zbMATH DE number 878894

Cites work

• 2-Isomorphic Graphs
• A proof of the CSP dichotomy conjecture
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• Bi‐arc graphs and the complexity of list homomorphisms
• List homomorphisms to reflexive graphs
• On the complexity of H-coloring
• Testing linear-invariant non-linear properties

Cited in

(5)

• A note on maxflow-mincut and homomorphic equivalence in matroids
• On the Complexity of Matroid Isomorphism Problems
• Matroid Complexity and Nonsuccinct Descriptions
• On the Complexity of Some Enumeration Problems for Matroids
• On the complexity of matroid isomorphism problem

This page was built for publication: The complexity of the matroid homomorphism problem

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