The complexity of matroid homomorphism reconfiguration

Abstract

We consider a reconfiguration version of the homomorphism problem ${\mathrm{Hom}}_{\mathbb{M}}(N)$ for binary matroids $N$. This reconfiguration problem, ${\mathrm{Recol}}_{\mathbb{M}}(N)$, asks, for two homomorphisms $\varphi$ and $\psi$ of a matroid $M$ to $N$, if there is a path of homomorphism from $\varphi$ 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 $\mathrm{PSPACE}$-complete when $N$ is the graphic matroid $M(K_3)$, $M(K_4)$, or any graphic matroid containing $M(K_5)$.