On the complexity of optimal matching reconfiguration

We consider the problem of matching reconfiguration, where we are given two matchings M<inf>s</inf> and M<inf>t</inf> in a graph G and the goal is to determine if there exists a sequence of matchings M<inf>0</inf>, M<inf>1</inf>,…, M<inf>l</inf>, such that M<inf>0</inf> = M<inf>s</inf>, all consecutive matchings differ by exactly two edges (specifically, any matching is obtained from the previous one by the addition and deletion of one edge), and M<inf>l</inf> = M<inf>t</inf>. It is known that the existence of such a sequence can be determined in polynomial time [5]. We extend the study of reconfiguring matchings to account for the length of the reconfiguration sequence. We show that checking if we can reconfigure M<inf>s</inf> to M<inf>t</inf> in at most l steps is NP-hard, even when the graph is unweighted, bipartite, and the maximum degree is four, and the matchings M<inf>s</inf> and M<inf>t</inf> are maximum matchings. We propose two simple algorithmic approaches, one of which improves on the brute-force running time while the other is a SAT formulation that we expect will be useful in practice.