The complexity of matroid homomorphism reconfiguration

Cheolwon Heo, Mark Siggers · 2025

Read The complexity of matroid homomorphism reconfiguration by Cheolwon Heo, Mark Siggers (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19181.txt.

Introduction

Cheolwon Heo and Mark Siggers wrote a 2025 mathematics paper on how hard it is to reshape one matroid map into another. Matroids are abstract structures that capture the idea of independence in sets. A homomorphism maps one matroid into another while keeping its structure, and the question is whether two such maps can be linked by small steps.

Each step may change the map on only one cocircuit at a time. The authors show the task is easy when the target shrinks down to the smallest graphic matroid. It turns fully hard, PSPACE-complete, for targets like the graphic matroids of small complete graphs or any that contain a larger one. The results draw a sharp line between easy and hard cases.

Catalog record

CREATORCheolwon Heo, Mark Siggers
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19181

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The complexity of matroid homomorphism reconfiguration Cheolwon Heo, Mark Siggers Abstract . We consider a reconfiguration version of the homomorphism problem Hom 𝕄 ​ ( N ) {\rm Hom}_{\mathbb{M}}(N) for binary matroids N N . This reconfiguration problem, Recol 𝕄 ​ ( N ) {\rm Recol}_{\mathbb{M}}(N) , asks, for two homomorphisms ϕ \phi and ψ \psi of a matroid M M to N 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 N . We show that this problem is trivial in the case that N N is, or dismantles to, the graphic matroid M ⁡ ( K 2 ) M(K_{2}) , and that the problem is PSPACE \PSPACE -complete when N N is the graphic matroid M ⁡ ( K 3 ) M(K_{3}) , M ⁡ ( K 4 ) M(K_{4}) , or any graphic matroid containing M ⁡ ( K 5 ) M(K_{5}) . 1. Introduction All matroids in this paper are binary matroids, meaning that they have a representation by a matrix over \mathbb{Z}_{2} ; and are simple, meaning the columns of the representing matrix are distinct. A homomorphism from a matroid M to a matroid N is a point map that takes cycles to cycles. More precisely, where the point space P(N) of a binary matroid is the vector space over \mathbb{Z}_{2} with basis E(N) , a point map \tau:E(M)\to E(N) extends linearly to map \tau of point spaces. This means that for sets X,Y\subset E(M) , \tau(X\cup Y) is the symmetric difference of \tau(X) and \tau(Y) . Definition 1.1 . For binary matroids M and N a matroid homomorphism \tau:M\to N is a point map \tau:E(M)\to E(N) such that for every circuit Z of M , \tau(Z) is a disjoint union of circuits of N . We consider the empty set to be the disjoint union of an empty set of circuits. We write M\to N to mean that there exists a matroid homomorphism \tau:M\to N . Though there are several notions of matroid colourings, we will, in analogue to the graph case, refer to matroid homomorphisms of M to N as N -colourings of M . We refer to the points of N as colours . 11 01 10 10 11 01 11 01 10 Example 1.2 . Never too early for a simple example, the figure above represents a matroid homomorphism of the graphic matroid M(K_{4}) to the graphic matroid M(K_{3}) . The points of M(K_{3}) are the non-zero points \{\begin{bmatrix}0\\ 1\end{bmatrix},\begin{bmatrix}1\\ 0\end{bmatrix},\begin{bmatrix}1\\ 1\end{bmatrix}\} of \mathbb{Z}_{2}^{2} (which we write compactly as \{01,10,11\} ). These are the colours that we map the points of M(K_{4}) to. The colours sum over any circuit, as vectors over \mathbb{Z}_{2} , to the zero vector 00 . So this represents a matroid homomorphism. It is not difficult to see that a graph homomorphism \phi:G\to H induces a matroid homomorphism \phi_{\mathbb{M}}:M(G)\to M(H) of the corresponding graphic matroids by mapping a point (edge) uv of M(G) to the point \phi_{\mathbb{M}}(uv):=\phi(u)\phi(v) of M(H) . On the other hand, a matroid homomorphism M(G)\to M(H) need not imply a graph homomorphism G\to H . Indeed Example 1.2 is a prime example of this, it gives a matroid homomorphism of M(K_{4}) to M(K_{3}) , while clearly there is no graph homomorphism of K_{4} to K_{3} . There is, however, a familiar duality relating N -colourings of a graphic matroid M(G) to H -colourings of the graph G . One will notice that the condition that the colours on points of M(K_{4}) sum to 0 on circuits is exactly the condition that makes this nowhere- 0 colouring of the edges of K_{4} a \mathbb{Z}_{2}^{2} -tension from Tutte’s classic work in [ 11 ] . Indeed, for graphic matroids, our definition of a matroid homomorphism correspond with the notion of a cyclic map from [ 9 ] , a \mathbb{Z}_{2} -tension continuous map from [ 6 ] (this follows from Theorem 3.1 of their paper, and Lemma 3.1 of ours), and a cut continuous map from [ 10 ] . All these works build on [ 11 ] . This basic setup of Tutte’s duality is generalised by the notion of the decision graph, which we introduced in [ 8 ] , only to notice later that it generalises similar constructions for graphic matroids from [ 6 ] . Defined in Section 4 , the decision graph D(N) , for a matroid N , has the following property for any graph G , G\to D(N)\iff M(G)\to N. In [ 8 ] we used the decision graph to address the complexity of the problem \mHom(N) , for fixed N , of deciding if a given matroid M admits an N -colouring. The complexity of the problem \mHom(N) for a matrix N was shown to be polynomial time solvable if N has a loop, or is bipartite, and was shown to be \NP -complete otherwise. This follows the dichotomy of the analogous result for graph homomorphisms from [ 7 ] , and follows quickly from this result using the decision graph D(N) of a matroid N . For those unfamiliar with Tutte’s duality, the following is an elementary example described using the decision graph. Example 1.3 . The clique K_{4} is the decision graph D(M(K_{3})) for the graphic matroid M(K_{3}) of K_{3} . Indeed, using the representation of M(K_{3}) over \mathbb{Z}_{2} by the matrix A=\begin{bmatrix}0&1&1\\ 1&0&1\end{bmatrix} as in Example 1.2 , label the vertices of K_{4} with the columns, or points, \{00,01,10,11\} of \mathbb{Z}_{2}^{2} . For a graph homomorphism \phi:G\to K_{4} we get a matroid homomorphism \tau_{\phi}:M(G)\to M(K_{3}) by \tau_{\phi}(uv)=\phi(u)+\phi(v) . On the other hand, for \tau:M(G)\to K_{3} we get a graph homomorphism \phi_{\tau}:G\to K_{4} by setting \phi(v_{0})=00 and then recursively defining \phi_{\tau} on a vertex v of G by setting \phi_{\tau}(v)=\phi_{\tau}(v^{\prime})+\tau(v^{\prime}v) where v^{\prime} is the precursor of v in a fixed spanning tree of G rooted at v_{0} . See Figure 1 for an example of a K_{3} -colouring of a graph G , the M(K_{4}) -colouring \tau_{\phi} it defines on M(G) , and the K_{3} -colouring \phi_{\tau_{\phi}} of G that \tau_{\phi} defines. Notice that \phi and \phi_{\tau_{\phi}} differ by the constant 11 . 10 11 10 11 01 \phi 01 01 01 10 11 11 \tau_{\phi} 01 00 01 00 10 \phi_{\tau_{\phi}} Figure 1. A K_{4} -colouring \phi of a graph G , the M(K_{3}) -colouring \tau_{\phi} of M(G) that it defines, and the K_{4} -colouring \phi_{\tau_{\phi}} of G that \tau_{\phi} defines. Retraction and list variations of the problem \Hom_{M}(N) were also considered in [ 8 ] ; for these variations, while the decision graph was still the main tool, there were several differences between the graph and matroid versions of the problem. In this paper we look a reconfiguration version of \Hom_{M}(H) In a reconfiguration version of a decision problem, one does not look to decide if there is a solution to an instance, but looks to decide if there is series of small changes one can make to get between a given pair of solutions. One well known reconfiguration version of the graph colouring problem \gHom(H) is the graph recolouring problem \gRecol(H) . Where

Read the complete text