The complexity of the matroid homomorphism problem (Q6162136)

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.