-
Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems
Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems
In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$, we prove a complexity dichotomy for the problem $\rm{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 …