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
2149951504 1846975517 2962926282 2568898402 2962964818 1987750368 2757068865 2258225879 2110762325 2912916233 2163548699
The 8-puzzle and the 15-puzzle have been used for many years as a domain for testing heuristic search techniques. From experience it is known that these puzzles are "difficult" and therefore useful for testing search techniques. In this paper we give strong evidence that these puzzles are indeed good test problems. We extend the 8-puzzle and the 15-puzzle to a nxn board and show that finding a shortest solution for the extended puzzle is NP-hard and thus computationally infeasible. We also present an approximation algorithm for transforming boards that is guaranteed to use no more than c L (SP) moves, where L (SP) is the length of the shortest solution and c is a constant which is independent of the given boards and their size n. Pancake Flipping is the problem of sorting a stack of pancakes of different sizes (that is, a permutation), when the only allowed operation is to insert a spatula anywhere in the stack and to flip the pancakes above it (that is, to perform a prefix reversal). In the burnt variant, one side of each pancake is marked as burnt, and it is required to finish with all pancakes having the burnt side down. Computing the optimal scenario for any stack of pancakes and determining the worst-case stack for any stack size have been challenges for over more than three decades. Beyond being an intriguing combinatorial problem in itself, it also yields applications, e.g. in parallel computing and computational biology. In this paper, we show that the Pancake Flipping problem, in its original (unburnt) variant, is NP-hard, thus answering the long-standing question of its computational complexity. Given a graph G=(V,E) with V= 1,...,n , we place on every vertex a token T_1,...,T_n. A swap is an exchange of tokens on adjacent vertices. We consider the algorithmic question of finding a shortest sequence of swaps such that token T_i is on vertex i. We are able to achieve essentially matching upper and lower bounds, for exact algorithms and approximation algorithms. For exact algorithms, we rule out any 2^ o(n) algorithm under the ETH. This is matched with a simple 2^ O(n*log(n)) algorithm based on a breadth-first search in an auxiliary graph. We show one general 4-approximation and show APX-hardness. Thus, there is a small constant delta > 1 such that every polynomial time approximation algorithm has approximation factor at least delta. Our results also hold for a generalized version, where tokens and vertices are colored. In this generalized version each token must go to a vertex with the same color. 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. In this work we consider triangulations of point sets in the Euclidean plane, i.e., maximal straight-line crossing-free graphs on a finite set of points. Given a triangulation of a point set, an edge flip is the operation of removing one edge and adding another one, such that the resulting graph is again a triangulation. Flips are a major way of locally transforming triangular meshes. We show that, given a point set S in the Euclidean plane and two triangulations T"1 and T"2 of S, it is an APX-hard problem to minimize the number of edge flips to transform T"1 to T"2. Given a Boolean formula and a satisfying assignment, a flip is an operation that changes the value of a variable in the assignment so that the resulting assignment remains satisfying. We study the problem of computing the shortest sequence of flips (if one exists) that transforms a given satisfying assignment @math to another satisfying assignment @math of an input Boolean formula. Earlier work characterized the complexity of deciding the existence of a sequence of flips between two given satisfying assignments using Schaefer's framework for classification of Boolean formulas. We build on it to provide a trichotomy for the complexity of finding the shortest sequence of flips and show that it is either in P, NP-complete, or PSPACE-complete. Our result adds to the growing set of complexity results known for shortest reconfiguration sequence problems by providing an example where the shortest sequence can be found in polynomial time even though the sequence flips variables that have the same value in both @math an... 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. 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.