The complexity of the matroid homomorphism problem (Q6162136)
From MaRDI portal
scientific article; zbMATH DE number 7696233
Language | Label | Description | Also known as |
---|---|---|---|
English | The complexity of the matroid homomorphism problem |
scientific article; zbMATH DE number 7696233 |
Statements
The complexity of the matroid homomorphism problem (English)
0 references
15 June 2023
0 references
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.
0 references
binary matroid
0 references
matroid homomorphism
0 references