Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.
Matching reconfiguration was initiated by the work of @cite_3 . They proposed the model of reconfiguration, in which we are also given an integer @math , and the vertex set of the configuration space consists of the matchings of size at least @math . Precisely, their model is defined in a slightly different way, but it is essentially the same as this definition. Two matchings @math and @math are adjacent if and only if they differ in only one edge. @cite_3 proved that the reachability of two given matchings can be checked in polynomial time.
@cite_3
1997048861
Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time.