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
2803094153 2568898402 2942216670 2145799305
Consider a graph such that each vertex has a nonnegative integer capacity and each edge has a positive integer weight. Then, a b-matching in the graph is a multi-set of edges (represented by an integer vector on edges) such that the total number of edges incident to each vertex is at most the capacity of the vertex. In this paper, we study a reconfiguration variant for maximum-weight b-matchings: For two given maximum-weight b-matchings in a graph, we are asked to determine whether there exists a sequence of maximum-weight b-matchings in the graph between them, with subsequent b-matchings obtained by removing one edge and adding another. We show that this reconfiguration problem is solvable in polynomial time for instances with no integrality gap. Such instances include bipartite graphs with any capacity function on vertices, and 2-matchings in general graphs. Thus, our result implies that the reconfiguration problem for maximum-weight matchings can be solved in polynomial time for bipartite graphs. The (k )-colouring reconfiguration problem asks whether, for a given graph (G ), two proper (k )-colourings ( ) and ( ) of (G ), and a positive integer ( ), there exists a sequence of at most ( ) proper (k )-colourings of (G ) which starts with ( ) and ends with ( ) and where successive colourings in the sequence differ on exactly one vertex of (G ). We give a complete picture of the parameterized complexity of the (k )-colouring reconfiguration problem for each fixed (k ) when parameterized by ( ). First we show that the (k )-colouring reconfiguration problem is polynomial-time solvable for (k=3 ), settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all (k 4 ), we show that the (k )-colouring reconfiguration problem, when parameterized by ( ), is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses. We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as @math -free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time. We study problems of reconfigurability of independent sets in graphs. We consider three different models (token jumping, token sliding, and token addition and removal) and analyze relationships between them. We prove that independent set reconfigurability in perfect graphs (under any of the three models) generalizes the shortest path reconfigurability problem in general graphs and is therefore PSPACE-complete. On the positive side, we give polynomial results for even-hole-free graphs and P"4-free graphs.