Book contents
- Frontmatter
- Contents
- Preface
- 1 Graph removal lemmas
- 2 The geometry of covering codes: small complete caps and saturating sets in Galois spaces
- 3 Bent functions and their connections to combinatorics
- 4 The complexity of change
- 5 How symmetric can maps on surfaces be?
- 6 Some open problems on permutation patterns
- 7 The world of hereditary graph classes viewed through Truemper configurations
- 8 Structure in minor-closed classes of matroids
- 9 Automatic counting of tilings of skinny plane regions
- References
4 - The complexity of change
Published online by Cambridge University Press: 05 July 2013
Book contents
- Frontmatter
- Contents
- Preface
- 1 Graph removal lemmas
- 2 The geometry of covering codes: small complete caps and saturating sets in Galois spaces
- 3 Bent functions and their connections to combinatorics
- 4 The complexity of change
- 5 How symmetric can maps on surfaces be?
- 6 Some open problems on permutation patterns
- 7 The world of hereditary graph classes viewed through Truemper configurations
- 8 Structure in minor-closed classes of matroids
- 9 Automatic counting of tilings of skinny plane regions
- References
Summary
Abstract
Many combinatorial problems can be formulated as “Can I transform configuration 1 into configuration 2, if only certain transformations are allowed?”. An example of such a question is: given two k-colourings of a graph, can I transform the first k-colouring into the second one, by recolouring one vertex at a time, and always maintaining a proper k-colouring? Another example is: given two solutions of a SAT-instance, can I transform the first solution into the second one, by changing the truth value one variable at a time, and always maintaining a solution of the SAT-instance? Other examples can be found in many classical puzzles, such as the 15-Puzzle and Rubik's Cube.
In this survey we shall give an overview of some older and some more recent work on this type of problem. The emphasis will be on the computational complexity of the problems: how hard is it to decide if a certain transformation is possible or not?
Introduction
Reconfiguration problems are combinatorial problems in which we are given a collection of configurations, together with some transformation rule(s) that allows us to change one configuration to another. A classic example is the so-called 15-puzzle (see Figure 1): 15 tiles are arranged on a 4 × 4 grid, with one empty square; neighbouring tiles can be moved to the empty slot. The normal aim is, given an initial configuration, to move the tiles to the position with all numbers in order (right-hand picture in Figure 1). Readers of a certain age may remember Rubik’s cube and its relatives as examples of reconfiguration puzzles (see Figure 2).
- Type
- Chapter
- Information
- Surveys in Combinatorics 2013 , pp. 127 - 160Publisher: Cambridge University PressPrint publication year: 2013
References
[1] and , Every planar map is four colourable. I. Discharging, Illinois J. Math. 21 (1977), 429–490.Google Scholar
[2] and , Every planar map is four colourable, Contemporary Mathematics 98 (1989), American Mathematical Society, Providence, RI.
[3] , , , Every planar map is four colourable. II. Reducibility, Illinois J. Math. 21 (1977), 491–567.Google Scholar
[4] , , , , A linear time algorithm for the feasibility of pebble motion on trees, Algorithmica 23 (1999), 223–245.Google Scholar
[5] and , Design of an efficient channel block retuning, Mobile Netw. Appl. 6 (2001), 501–510.Google Scholar
[6] , , and , Frequency reassignment in cellular phone networks, Smith Institute Study Group Report, available from www.smithinst.ac.uk/Projects/ESGI53/ESGI53-Motorola/Report, (2005).
[7] and , Graph Theory, Springer, New York (2008).
[8] and , Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances, Theoret. Comput. Sci. 410 (2009), 5215–5226.Google Scholar
[9] , , and , Connectedness of token graphs with labelled tokens. In preparation.
[10] and , A constrained Potts antiferromagnet model with an interface representation, J. Phys. A 30 (1997), 8385–8413.Google Scholar
[11] , Mixing Graph Colourings, PhD Thesis, London School of Economics, (2007).
[12] , , and , Connectedness of the graph of vertex-colourings, Discrete Math. 308 (2008), 913–919.Google Scholar
[13] , , and , Mixing 3-colourings in bipartite graphs, European J. Combin. 30 (2009), 1593–1606.Google Scholar
[16] Clay Mathematical Institute, The Millennium Prize Problems. www.claymath.org/millennium/.
[17] and , Graph folding, in Proceedings of the 10th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congress. Numer. XXIII–XXIV (1979), pp. 305–314.Google Scholar
[18] , Sokoban is PSPACE-complete, Technical Report TR 97–02, Department of Computing Science, University of Alberta, available via citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.52.41, (1997).
[19] , Hamilton circuits in tree graphs, IEEE Trans. Circuit Theory CT-13 (1966), 82–90.Google Scholar
[20] and , Playing games with algorithms: Algorithmic combinatorial game theory, arXiv:cs/0106019v2, (2008).
[21] , Graph Theory, Springer, Heidelberg (2010).
[22] , , , and , Randomly colouring sparse random graphs with fewer colours than the maximum degree, Random Structures Algorithms 29 (2006), 450–465.Google Scholar
[24] and , Antiferromagnetic Potts models on the square lattice: A high-precision Monte Carlo study, J. Statist. Phys. 96 (1999), 461–530.Google Scholar
[25] and , Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, New York (1979).
[26] , Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard, in Studies in Complexity and Cryptography; Miscellanea on the Interplay between Randomness and Computation, Lect. Notes Comput. Sci., 6650 (2011), pp. 1–5.Google Scholar
[27] , , , and , The connectivity of Boolean satisfiability: Computational and structural dichotomies, in Proceedings of Automata, Languages and Programming, 33rd International Colloquium, Lect. Notes Comput. Sci., 4051 (2006), pp. 346–357.Google Scholar
[28] , , , and , The connectivity of Boolean satisfiability: Computational and structural dichotomies, SIAM J. Comput. 38 (2009), 2330–2355.Google Scholar
[30] , Frequency assignment: Theory and applications, Proc. IEEE 68 (1980), 1497–1514.Google Scholar
[31] , Frequency reassignment problem in mobile communication networks, Comput. Oper. Res. 34 (2007), 2939–2948.Google Scholar
[32] and , PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation, Theoret. Comput. Sci. 343 (2005), 72–96.Google Scholar
[33] , , , , , , and , On the complexity of reconfiguration problems, Theoret. Comput. Sci. 412 (2011), 1054–1065.Google Scholar
[34] , A very simple algorithm for estimating the number of k-colourings of a low degree graph, Random Structures Algorithms 7 (1995), 157–165.Google Scholar
[35] , Counting, Sampling and Integrating: Algorithms and Complexity, Birkhäuser Verlag, Basel (2003).
[36] , , and , Random generation of combinatorial structures from a uniform distribution, Theoret. Comput. Sci. 43 (1986), 169–188.Google Scholar
[37] , , and , Coordinating pebble motion on graphs, the diameter of permutation groups, and applications, in Proceedings of the 25th Annual Symposium on Foundations of Computer Science (1984), pp. 241–250.
[38] and , Kempe classes and the Hadwiger Conjecture, J. Combin. Theory Ser. B 31 (1981), 95–104.Google Scholar
[39] and (eds.), Methods and Algorithms for Radio Channel Assignment, Oxford Univ. Press, Oxford (2003).
[40] and , Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings, J. Discrete Alg. 3 (2005), 92–100.Google Scholar
[41] , , and , On the Boolean connectivity problem for Horn relations, Discrete Appl. Math. 158 (2010), 2024–2030.Google Scholar
[42] and , The height and length of colour switching, in Graph Colouring and Applications (eds. and ), AMS, Providence (1999), pp. 101–110.
[43] , Les 5-colorations d'un graphe planaire forment une classe de commutation unique, J. Combin. Theory Ser. B 24 (1978), 251–257.Google Scholar
[44] , Kempe equivalence of colorings, in Graph theory in Paris (eds. , , , , and ), Birkhäuser Verlag, Basel (2007), 287–297.
[45] , Computational Complexity, Addison-Wesley, Boston (1994).
[46] , , , and , Motion planning on a graph, in Proceedings of the 35th Annual Symposium on Foundations of Computer Science (1994), pp. 511–520. Long version available online at: people.csail.mit.edu/madhu/papers/1994/robot-full.pdf.
[47] , Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci. 4 (1970), 177–192.Google Scholar
[48] , The complexity of satisfiability problems, in Proceedings of the 10th Annual ACM Symposium on Theory of Computing (1978), pp. 216–226.
[49] , Combinatorial Optimization; Polyhedra and Effciency, Springer-Verlag, Berlin (2003).
[50] , The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, in Surveys in Combinatorics 2005Cambridge Univ. Press, Cambridge (2005), pp. 173–226.
[51] and , k-Color multi-robot motion planning, arXiv:1202.6174v2, (2012).
[52] , Connectivity Properties of Some Transformation Graphs, PhD Thesis, London School of Economics, in preparation, (2013).
[53] , On an estimate of the chromatic class of a p-graph (in Russian), Metody Diskret. Analiz. 3 (1964), 25–30.Google Scholar
[55] , , , Three-state antiferromagnetic Potts models: A Monte Carlo study, Phys. Rev. B 42 (1990), 2465–2474.Google Scholar
[56] , Graph puzzles, homotopy, and the alternating group, J. Combin. Theory Ser. B 16 (1974), 86–96.Google Scholar
- 57
- Cited by