In discrete mathematics 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 In graph theory, reachability refers to the ability to get from one Vertex (graph theory), vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s) if there exists a sequence of Glossary of graph theory#Basics, ...

connectivity Connectivity may refer to: Computing and technology * Connectivity (media), the ability of the social media to accumulate economic capital from the users connections and activities * Internet connectivity, the means by which individual terminal ...

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 toy ...

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 for ...

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 converges to a discrete uniform distribution, 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 Z ...

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 In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has ...

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 Three-dimensional space, 3-D combination puzzle originally invented in 1974 by Hungarians, Hungarian sculptor and professor of architecture Ernő Rubik. Originally called the Magic Cube, the puzzle was licensed by Rubik t ...

. This type of puzzle can often be modeled mathematically using the theory of

permutation group In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...

s, 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 is a puzzle video game in which the player pushes boxes around in a warehouse, trying to get them to storage locations. The game was designed in 1981 by Hiroyuki Imabayashi, and first published in December 1982. Gameplay The game is played on a ...

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 In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can b ...

. *

Rotation distance In discrete mathematics and theoretical computer science, the rotation distance between two binary trees with the same number of nodes is the minimum number of tree rotations needed to reconfigure one tree into another. Because of a combinatorial e ...

binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...

s and related problems of flip distance in

flip graph In mathematics, a flip graph is a graph whose vertices are combinatorial or geometric objects, and whose edges link two of these objects when they can be obtained from one another by an elementary operation called a flip. Flip graphs are spec ...

s. 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 o ...

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 Kempe may refer to: * Kempe baronets, a title in the Baronetage of England * Kempe chain, part of the four-colour theorem * Kempe Fjord, King Christian X Land, Greenland * Kempe Glacier, Antarctica * Kempe Hill, former name of Camp Hill, West Mi ...

. 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 In the mathematics of graph coloring, Cereceda’s conjecture is an unsolved problem on the distance between pairs of colorings of sparse graphs. It states that, for two different colorings of a graph of degeneracy , both using at most colors, ...

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 In Computational complexity theory, complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-comple ...

, 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 In theoretical computer science, nondeterministic constraint logic is a combinatorial system in which an orientation is given to the edges of a weighted undirected graph, subject to certain constraints. One can change this orientation by steps in ...

is a combinatorial problem on

orientations ''Orientations'' is a bimonthly print magazine published in Hong Kong and distributed worldwide since 1969. It is an authoritative source of information on the many and varied aspects of the arts of East and Southeast Asia, the Himalayas, the India ...

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bi ...

s 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 In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...

-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 Bandwidth commonly refers to: * Bandwidth (signal processing) or ''analog bandwidth'', ''frequency bandwidth'', or ''radio bandwidth'', a measure of the width of a frequency range * Bandwidth (computing), the rate of data transfer, bit rate or thr ...

. These hardness results are often used as the basis of

reductions Reductions ( es, reducciones, also called ; , pl. ) were settlements created by Spanish rulers and Roman Catholic missionaries in Spanish America and the Spanish East Indies (the Philippines). In Portuguese-speaking Latin America, such redu ...

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 geome ...

, 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 Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...

, 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