The complexity of matroid homomorphism reconfiguration
We consider a reconfiguration version of the homomorphism problem ${\rm Hom}_\mathbb{M}(N)$ for binary matroids $N$. This reconfiguration problem, ${\rm Recol}_\mathbb{M}(N)$, asks, for two homomorphisms $\phi$ and $\psi$ of a matroid $M$ to $N$, if there is a path of homomorphism from $\phi$ to $\psi$ such that consecutive homomorphism in the path differ on a single cocircuit of $N$. We show that this problem is trivial in the case that $N$ dismantles to the graphic matroid $M(K_2)$, and that the problem is ${\rm PSPACE}$-complete when $N$ is the graphic matroid $M(K_3)$, $M(K_4)$, or any graphic matroid containing $M(K_5)$.
Publication Details
- Journal
- ArXiv.org
- Published
- 2025-03-24
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00