Reconfiguration

<h2 id="types-of-problems">Types of problems</h2>
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:

<ul><li>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 <a href="/facts/Computational_complexity/Qenh22Ja">computational complexity</a> of determining whether the state space for a particular problem is connected?</li>
<li>What is the <a href="/facts/Diameter/6uNn4VmU">diameter</a> of the state space, the smallest number D such that every two states can be transformed into each other with at most D moves?</li>
<li>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?</li>
<li>If moves are chosen randomly with a carefully chosen probability distribution so that the resulting <a href="/facts/Markov_chain/5oP5hntk">Markov chain</a> converges to a <a href="/facts/Discrete_uniform_distribution/M52SQP5n">discrete uniform distribution</a>, how many moves are needed in a <a href="/facts/Random_walk/08v0jmfv">random walk</a> in order to ensure that the state at the end up the walk is nearly uniformly distributed? That is, what is the <a href="/facts/Markov_chain_mixing_time/LulyNjQT">Markov chain mixing time</a>?</li></ul>
<h2 id="examples">Examples</h2>
Examples of problems studied in reconfiguration include:

<ul><li>Games or puzzles such as the <a href="/facts/15_puzzle/kyFRwRWs">15 puzzle</a> or <a href="/facts/Rubik%2527s_cube/Nlq35AbS">Rubik's cube</a>. This type of puzzle can often be modeled mathematically using the theory of <a href="/facts/Permutation_group/vRsNNwwx">permutation groups</a>, 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 
 
 
 
 n
 ×
 n
 ×
 n
 
 
 {\displaystyle n\times n\times n}
 
 version's of the Rubik's cube, the state space diameter is 
 
 
 
 Θ
 (
 
 n
 
 2
 
 
 
 /
 
 log
 ⁡
 n
 )
 
 
 {\displaystyle \Theta (n^{2}/\log n)}
 
, 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 <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> Other reconfiguration puzzles such as <a href="/facts/Sokoban/T1G50XgG">Sokoban</a> may be modeled as <a href="/facts/Token_reconfiguration/X92Fc3MD">token reconfiguration</a> but lack a group-theoretic structure. For such problems, the complexity can be higher; in particular, testing reachability for Sokoban is <a href="/facts/PSPACE-complete/gkV3vHfX">PSPACE-complete</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a></li>
<li><a href="/facts/Rotation_distance/fl31kBMG">Rotation distance</a> in <a href="/facts/Binary_tree/TDV7GMpu">binary trees</a> and related problems of <a href="/facts/Flip_distance/ldf8Bfbl">flip distance</a> in <a href="/facts/Flip_graph/X7r9D8jx">flip graphs</a>. 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 <a href="/facts/Binary_search_tree/gWubNt7b">binary search trees</a>. 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,<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> but it remains an open problem whether the rotation distance between two arbitrary trees can be found in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> The analogous problems for flip distance between triangulations of point sets or non-convex polygons are NP-hard.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>Reconfiguration of <a href="/facts/Graph_coloring/J6HoBfP0">graph colorings</a>. The moves that have been considered for coloring reconfiguration include changing the color of a single vertex, or swapping the colors of a <a href="/facts/Kempe_chain/avKtH0Gy">Kempe chain</a>. When the number of colors is at least two plus the <a href="/facts/Degeneracy_(graph_theory)/IaYkus22">degeneracy</a> of a graph, then the state space of single-vertex recolorings is connected, and <a href="/facts/Cereceda%2527s_conjecture/fVuNlLaI">Cereceda's conjecture</a> 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 <a href="/facts/Co-NP-complete/oGepXz5C">co-NP-complete</a>,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> but when two colorings can be reconfigured to each other, the shortest reconfiguration sequence can be found in polynomial time.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> For more than three colors, single-vertex reconfiguration is PSPACE-complete.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li>
<li><a href="/facts/Nondeterministic_constraint_logic/6zAAzIho">Nondeterministic constraint logic</a> is a combinatorial problem on <a href="/facts/Orientation_(graph_theory)/GV2KdNtn">orientations</a> of <a href="/facts/Cubic_graph/6M32WUIJ">cubic graphs</a> 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 <a href="/facts/PSPACE/RIkAClvG">PSPACE</a>-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 <a href="/facts/Graph_bandwidth/ugGo2j8l">bandwidth</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> These hardness results are often used as the basis of <a href="/facts/Reduction_(complexity)/IVWF7a1c">reductions</a> proving that other reconfiguration problems, such as the ones arising from games and puzzles, are also hard.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://reconf.wikidot.com/">Combinatorial Reconfiguration Resources</a> (including <a href="http://reconf.wikidot.com/papers">a non-exhaustive bibliography</a>)</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn: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, ISBN 978-3-642-23718-8, MR 2893242, S2CID 664306 <a href="978-3-642-23718-8" target="_blank">978-3-642-23718-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/Advances_in_Mathematics" target="_blank">/wiki/Advances_in_Mathematics</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/Anna_Lubiw" target="_blank">/wiki/Anna_Lubiw</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/Discrete_%26_Computational_Geometry" target="_blank">/wiki/Discrete_%26_Computational_Geometry</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Cereceda, Luis (2007), Mixing graph colourings, doctoral dissertation, London School of Economics. See especially page 109. <a href="http://etheses.lse.ac.uk/131/" target="_blank">http://etheses.lse.ac.uk/131/</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="http://dro.dur.ac.uk/15595/1/15595.pdf" target="_blank">http://dro.dur.ac.uk/15595/1/15595.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn: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 <a href="/wiki/Bob_Hearn" target="_blank">/wiki/Bob_Hearn</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
</ol>

Reconfiguration open-in-new

Reconfiguration