The complexity of the matroid homomorphism problem

Cheolwon Heo, Hyobeen Kim, Mark Siggers

Research output: Contribution to journalArticlepeer-review

Abstract

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 HomM(N) of deciding if a binary matroid M admits a matroid 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.

Original languageEnglish
Article numberP2.27
JournalElectronic Journal of Combinatorics
Volume30
Issue number2
DOIs
StatePublished - 2023

Fingerprint

Dive into the research topics of 'The complexity of the matroid homomorphism problem'. Together they form a unique fingerprint.

Cite this