discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continu ...

and

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, reconfiguration problems are computational problems involving reachability or connectivity of

state space A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory. For instance, the t ...

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 In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

of determining whether the state space for a particular problem is connected? *What is the

diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...

of the state space, the smallest number such that every two states can be transformed into each other with at most 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 A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...

converges to a

discrete uniform distribution In probability theory and statistics, the discrete uniform distribution is a symmetric probability distribution wherein a finite number of values are equally likely to be observed; every one of ''n'' values has equal probability 1/''n''. Ano ...

, how many moves are needed in a

random walk In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb ...

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 The Rubik's Cube is a 3-D combination puzzle originally invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik. Originally called the Magic Cube, the puzzle was licensed by Rubik to be sold by Pentangle Puzzles in t ...

. 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

n\times n\times n

version's of the Rubik's cube, the state space diameter is

\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

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

. Other reconfiguration puzzles such as Sokoban may be modeled as

token reconfiguration In computational complexity theory and combinatorics, the token reconfiguration problem is a reconfiguration problem on a graph with both an initial and desired state for tokens. Given a graph G, an initial state of tokens is defined by a subset V ...

but lack a group-theoretic structure. For such problems, the complexity can be higher; in particular, testing reachability for Sokoban is PSPACE-complete. * 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 tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...

s. 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, but it remains an open problem whether the rotation distance between two arbitrary trees can be found in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

. The analogous problems for flip distance between triangulations of point sets or non-convex polygons are NP-hard. *Reconfiguration of

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

s. 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, but when two colorings can be reconfigured to each other, the shortest reconfiguration sequence can be found in polynomial time. For more than three colors, single-vertex reconfiguration is PSPACE-complete. * 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. 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.

References

{{reflist, refs= {{citation , last1 = Bonsma , first1 = Paul , last2 = Cereceda , first2 = Luis , doi = 10.1016/j.tcs.2009.08.023 , issue = 50 , journal = Theoretical Computer Science , mr = 2573973 , pages = 5215–5226 , title = Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances , volume = 410 , year = 2009, doi-access = free {{citation, title=Mixing graph colourings, first=Luis, last=Cereceda, series=doctoral dissertation, publisher=London School of Economics, year=2007, url=http://etheses.lse.ac.uk/131/. See especially page 109. {{citation , last1 = Johnson , first1 = Matthew , last2 = Kratsch , first2 = Dieter , last3 = Kratsch , first3 = Stefan , last4 = Patel , first4 = Viresh , last5 = Paulusma , first5 = Daniël , doi = 10.1007/s00453-015-0009-7 , issue = 2 , journal = Algorithmica , mr = 3506195 , pages = 295–321 , title = Finding shortest paths between graph colourings , volume = 75 , year = 2016 {{citation , last1 = Kanj , first1 = Iyad , last2 = Sedgwick , first2 = Eric , last3 = Xia , first3 = Ge , doi = 10.1007/s00454-017-9867-x , issue = 2 , journal =

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ge ...

, mr = 3679938 , pages = 313–344 , title = Computing the flip distance between triangulations , volume = 58 , year = 2017, arxiv = 1407.1525 {{citation , last = van der Zanden , first = Tom C. , arxiv = 1509.02683 , contribution = Parameterized complexity of graph constraint logic , doi = 10.4230/LIPIcs.IPEC.2015.282 , mr = 3452428 , pages = 282–293 , publisher = Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern , series = LIPIcs. Leibniz Int. Proc. Inform. , title = 10th International Symposium on Parameterized and Exact Computation , volume = 43 , year = 2015 {{citation , last1 = Hearn , first1 = Robert A. , last2 = Demaine , first2 = Erik D. , author2-link = Erik Demaine , doi = 10.1016/j.tcs.2005.05.008 , issue = 1–2 , journal =

Theoretical Computer Science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, mr = 2168845 , pages = 72–96 , title = PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation , volume = 343 , year = 2005, arxiv = cs/0205005 {{citation , last1 = Lubiw , first1 = Anna , author1-link = Anna Lubiw , last2 = Pathak , first2 = Vinayak , doi = 10.1016/j.comgeo.2014.11.001 , journal = Computational Geometry , mr = 3399985 , pages = 17–23 , title = Flip distance between two triangulations of a point set is NP-complete , volume = 49 , year = 2015, doi-access = free {{citation , last1 = Aichholzer , first1 = Oswin , last2 = Mulzer , first2 = Wolfgang , last3 = Pilz , first3 = Alexander , doi = 10.1007/s00454-015-9709-7 , issue = 2 , journal =

, mr = 3372115 , pages = 368–389 , title = Flip distance between triangulations of a simple polygon is NP-complete , volume = 54 , year = 2015, arxiv = 1209.0579 {{citation , last = Pournin , first = Lionel , doi = 10.1016/j.aim.2014.02.035 , journal =

Advances in Mathematics ''Advances in Mathematics'' is a peer-reviewed scientific journal covering research on pure mathematics. It was established in 1961 by Gian-Carlo Rota. The journal publishes 18 issues each year, in three volumes. At the origin, the journal aimed ...

, mr = 3197650 , pages = 13–42 , title = The diameter of associahedra , volume = 259 , year = 2014, doi-access = free {{citation , last1 = Demaine , first1 = Erik D. , author1-link = Erik Demaine , last2 = Demaine , first2 = Martin L. , author2-link = Martin Demaine , last3 = Eisenstat , first3 = Sarah , last4 = Lubiw , first4 = Anna , author4-link = Anna Lubiw , last5 = Winslow , first5 = Andrew , arxiv = 1106.5736 , contribution = Algorithms for solving Rubik's cubes , doi = 10.1007/978-3-642-23719-5_58 , mr = 2893242 , pages = 689–700 , publisher = Springer, Heidelberg , series = Lecture Notes in Computer Science , title = Algorithms – ESA 2011: 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011, Proceedings , volume = 6942 , year = 2011 {{citation , last = Culberson , first = Joseph , doi = 10.7939/R3JM23K33 , publisher = University of Alberta, Department of Computing Science , series = Technical report TR97-02 , title = Sokoban is PSPACE-complete , year = 1997, hdl = 10048/27119 , hdl-access = free

External Links

Combinatorial Reconfiguration Resources
(includin
a non-exhaustive bibliography