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 continuous f ...

and

theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

, reconfiguration problems are computational problems involving

reachability In graph theory, reachability refers to the ability to get from one 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 adjacent vertices (i.e. a walk) which starts with s a ...

or connectivity of

state space In computer science, a state space is a discrete space representing 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 ...

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 centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

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 In probability theory and statistics, a Markov chain or Markov process is a stochastic process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally ...

converges to a

discrete uniform distribution In probability theory and statistics, the discrete uniform distribution is a symmetric probability distribution wherein each of some finite whole number ''n'' of outcome values are equally likely to be observed. Thus every one of the ''n'' out ...

, how many moves are needed in a

random walk In mathematics, a random walk, sometimes known as a drunkard's walk, is a stochastic process that describes a path that consists of a succession of random steps on some Space (mathematics), mathematical space. An elementary example of a rand ...

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

Examples

Examples of problems studied in reconfiguration include: *Games or puzzles such as the

15 puzzle The 15 puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and more) is a sliding puzzle. It has 15 square tiles numbered 1 to 15 in a frame that is 4 tile positions high and 4 tile positions wide, with one unoccupied pos ...

or Rubik's cube. 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 ...

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, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

. 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 Japan in 1982 by his company Thinking Rabbit for ...

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 (PSPACE, polynomial space) and if every other problem that can be solved in polynomial sp ...

. *

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 tree data structure in which each node has at most two children, referred to as the ''left child'' and the ''right child''. That is, it is a ''k''-ary tree with . A recursive definition using set theor ...

s and related problems of

flip distance In discrete mathematics and theoretical computer science, the flip distance between two triangulations of the same point set is the number of flips required to transform one triangulation into another. A flip removes an edge between two triangles ...

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 tree, rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left ...

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 theoretical 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 p ...

. 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 methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...

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 In mathematics, a Kempe chain is a device used mainly in the study of the four colour theorem. Intuitively, it is a connected chain of vertices on a graph with alternating colours. History Kempe chains were first used by Alfred Kempe in his atte ...

. 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 (graph theory), degeneracy , bo ...

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 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-complete problem with only polynomial ...

, 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 i ...

is a combinatorial problem on

orientations ''Orientations'' is a bimonthly print magazine published in Hong Kong and distributed worldwide since 1969. History ''Orientations'' was launched in 1969 by Adrian Zecha (who was later the founder of Aman Resorts) to showcase Asian art and cu ...

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

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(''f''(''n'')), the set of all problems that can ...

-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 (, also called ; ) were settlements established by Spanish rulers and Roman Catholic missionaries in Spanish America and the Spanish East Indies (the Philippines). In Portuguese-speaking Latin America, such reductions were also ...

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 = {{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, s2cid = 253974066 , url = http://dro.dur.ac.uk/15595/1/15595.pdf {{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 ...

, mr = 3679938 , pages = 313–344 , title = Computing the flip distance between triangulations , volume = 58 , year = 2017, arxiv = 1407.1525 , s2cid = 254033552 {{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 , doi-access = free , s2cid = 15959029 {{citation , last1 = Hearn , first1 = Robert A. , author1-link = Bob Hearn , 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 is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

, 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 , s2cid = 656067 {{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 , arxiv = 1205.2425 {{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 , s2cid = 254037222 {{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 , arxiv = 1207.6296 {{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, isbn = 978-3-642-23718-8 , s2cid = 664306 {{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