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.
Shortest reconfiguration has attracted considerable attention. Starting from an old work on the @math -puzzle @cite_30 , we see the work on pancake sorting @cite_37 , triangulations of point sets @cite_19 @cite_36 and simple polygons @cite_11 under flip distances, and also independent set reconfigurations @cite_6 , satisfiability reconfiguration @cite_17 , coloring reconfiguration @cite_33 , token swapping problems @cite_16 @cite_14 @cite_23 @cite_20 @cite_27 @cite_22 . A tantalizing open problem is to determine the complexity of computing the rotation distance of two rooted binary trees (or equivalently the flip distance of two triangulations of a convex polygon, or the combinatorial shortest path of an associahedron).
@cite_30 @cite_37 @cite_14 @cite_33 @cite_22 @cite_36 @cite_17 @cite_6 @cite_19 @cite_27 @cite_23 @cite_16 @cite_20 @cite_11
2163548699 2258225879 2110762325 2942216670
Let T be a triangulation of a simple polygon. A flip in T is the operation of replacing one diagonal of T by a different one such that the resulting graph is again a triangulation. The flip distance between two triangulations is the smallest number of flips required to transform one triangulation into the other. For the special case of convex polygons, the problem of determining the shortest flip distance between two triangulations is equivalent to determining the rotation distance between two binary trees, a central problem which is still open after over 25 years of intensive study. We show that computing the flip distance between two triangulations of a simple polygon is NP-hard. This complements a recent result that shows APX-hardness of determining the flip distance between two triangulations of a planar point set. For given two independent sets ( I _b ) and ( I _r ) of a graph, the sliding token problem is to determine if there exists a sequence of independent sets which transforms ( I _b ) into ( I _r ) so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. The sliding token problem is one of the reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. These problems tend to be PSPACE-complete in general, and some polynomial time algorithms are shown in restricted cases. Recently, the problems for finding a shortest reconfiguration sequence are investigated. For the 3SAT reconfiguration problem, a trichotomy for the complexity of finding the shortest sequence has been shown; it is in P, NP-complete, or PSPACE-complete in certain conditions. Even if it is polynomial time solvable to decide whether two instances are reconfigured with each other, it can be NP-complete to find a shortest sequence between them. We show nontrivial polynomial time algorithms for finding a shortest sequence between two independent sets for some graph classes. As far as the authors know, one of them is the first polynomial time algorithm for the shortest sliding token problem that requires detours of tokens. Given two triangulations of a convex polygon, computing the minimum number of flips required to transform one to the other is a long-standing open problem. It is not known whether the problem is in P or NP-complete. We prove that two natural generalizations of the problem are NP-complete, namely computing the minimum number of flips between two triangulations of (1) a polygon with holes; (2) a set of points in the plane. 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.