In discrete mathematics and theoretical computer science, reconfiguration problems are computational problems involving reachability or connectivity of state spaces.

Types of problems

Here, a state space is a discrete set of configurations of a system or solutions of a combinatorial problem, called states, together with a set of allowed moves linking one state to another. Reconfiguration problems may ask:

  • For a given class of problems, is the state space always connected? That is, can one transform every pair of states into each other with a sequence of moves? If not, what is the computational complexity of determining whether the state space for a particular problem is connected?
  • What is the diameter of the state space, the smallest number D such that every two states can be transformed into each other with at most D moves?
  • Given two states, what is the complexity of determining whether they can be transformed into each other, or of finding the shortest sequence of moves for transforming one into another?
  • If moves are chosen randomly with a carefully chosen probability distribution so that the resulting Markov chain converges to a discrete uniform distribution, how many moves are needed in a random walk in order to ensure that the state at the end up the walk is nearly uniformly distributed? That is, what is the Markov chain mixing time?

Examples

Examples of problems studied in reconfiguration include:

  • Games or puzzles such as the 15 puzzle or Rubik's cube. This type of puzzle can often be modeled mathematically using the theory of permutation groups, leading to fast algorithms for determining whether states are connected; however, finding the state space diameter or the shortest path between two states may be more difficult. For instance, for version's of the Rubik's cube, the state space diameter is , and the complexity of finding shortest solutions is unknown, but for a generalized version of the puzzle (in which some cube faces are unlabeled) it is NP-hard.[1] Other reconfiguration puzzles such as Sokoban may be modeled as token reconfiguration but lack a group-theoretic structure. For such problems, the complexity can be higher; in particular, testing reachability for Sokoban is PSPACE-complete.[2]
  • Rotation distance in binary trees and related problems of flip distance in flip graphs. A rotation is an operation that changes the structure of a binary tree without affecting the left-to-right ordering of its nodes, often used to rebalence binary search trees. Rotation distance is the minimum number of rotations needed to transform one tree into another. The same state space also models the triangulations of a convex polygon, and moves that "flip" one triangulation into another by removing one diagonal of the polygon and replacing it by another; similar problems have also been studied on other kinds of triangulation. The maximum possible rotation distance between two trees with a given number of nodes is known,[3] but it remains an open problem whether the rotation distance between two arbitrary trees can be found in polynomial time.[4] The analogous problems for flip distance between triangulations of point sets or non-convex polygons are NP-hard.[5][6]
  • Reconfiguration of graph colorings. The moves that have been considered for coloring reconfiguration include changing the color of a single vertex, or swapping the colors of a Kempe chain. When the number of colors is at least two plus the degeneracy of a graph, then the state space of single-vertex recolorings is connected, and Cereceda's conjecture suggests that it has polynomial diameter. For fewer colors, some graphs have disconnected state spaces. For 3-colorings, testing global connectivity of the single-vertex recoloring state space is co-NP-complete,[7] but when two colorings can be reconfigured to each other, the shortest reconfiguration sequence can be found in polynomial time.[8] For more than three colors, single-vertex reconfiguration is PSPACE-complete.[9]
  • Nondeterministic constraint logic is a combinatorial problem on orientations of cubic graphs whose edges are colored red and blue. In a valid state of the system, each vertex must have at least one blue edge or at least two edges coming into it. A move in this state space reverses the orientation of a single edge while preserving these constraints. It is PSPACE-complete to test whether the resulting state space is connected or whether two states are reachable from each other, even when the underlying graph has bounded bandwidth.[10] These hardness results are often used as the basis of reductions proving that other reconfiguration problems, such as the ones arising from games and puzzles, are also hard.[11]

References

  1. ↑ Demaine, Erik D.; Demaine, Martin L.; Eisenstat, Sarah; Lubiw, Anna; Winslow, Andrew (2011), "Algorithms for solving Rubik's cubes", Algorithms – ESA 2011: 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011, Proceedings, Lecture Notes in Computer Science, vol. 6942, Springer, Heidelberg, pp. 689–700, arXiv:1106.5736, doi:10.1007/978-3-642-23719-5_58, MR 2893242, S2CID 664306
  2. ↑ Culberson, Joseph (1997), Sokoban is PSPACE-complete, Technical report TR97-02, University of Alberta, Department of Computing Science, doi:10.7939/R3JM23K33, hdl:10048/27119
  3. ↑ Pournin, Lionel (2014), "The diameter of associahedra", Advances in Mathematics, 259: 13–42, arXiv:1207.6296, doi:10.1016/j.aim.2014.02.035, MR 3197650
  4. ↑ Kanj, Iyad; Sedgwick, Eric; Xia, Ge (2017), "Computing the flip distance between triangulations", Discrete & Computational Geometry, 58 (2): 313–344, arXiv:1407.1525, doi:10.1007/s00454-017-9867-x, MR 3679938, S2CID 254033552
  5. ↑ Lubiw, Anna; Pathak, Vinayak (2015), "Flip distance between two triangulations of a point set is NP-complete", Computational Geometry, 49: 17–23, arXiv:1205.2425, doi:10.1016/j.comgeo.2014.11.001, MR 3399985
  6. ↑ Aichholzer, Oswin; Mulzer, Wolfgang; Pilz, Alexander (2015), "Flip distance between triangulations of a simple polygon is NP-complete", Discrete & Computational Geometry, 54 (2): 368–389, arXiv:1209.0579, doi:10.1007/s00454-015-9709-7, MR 3372115, S2CID 254037222
  7. ↑ Cereceda, Luis (2007), Mixing graph colourings, doctoral dissertation, London School of Economics. See especially page 109.
  8. ↑ Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël (2016), "Finding shortest paths between graph colourings" (PDF), Algorithmica, 75 (2): 295–321, doi:10.1007/s00453-015-0009-7, MR 3506195, S2CID 253974066
  9. ↑ Bonsma, Paul; Cereceda, Luis (2009), "Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances", Theoretical Computer Science, 410 (50): 5215–5226, doi:10.1016/j.tcs.2009.08.023, MR 2573973
  10. ↑ van der Zanden, Tom C. (2015), "Parameterized complexity of graph constraint logic", 10th International Symposium on Parameterized and Exact Computation, LIPIcs. Leibniz Int. Proc. Inform., vol. 43, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, pp. 282–293, arXiv:1509.02683, doi:10.4230/LIPIcs.IPEC.2015.282, MR 3452428, S2CID 15959029
  11. ↑ Hearn, Robert A.; Demaine, Erik D. (2005), "PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation", Theoretical Computer Science, 343 (1–2): 72–96, arXiv:cs/0205005, doi:10.1016/j.tcs.2005.05.008, MR 2168845, S2CID 656067
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.