PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity of Change

Jan van den Heuvel

arXiv:1312.2816v1cs.DMmath.CO

TL;DR

Reconfiguration problems ask how hard it is to decide whether one feasible configuration can be transformed into another under allowed moves. This survey synthesizes results across puzzles, colourings, token systems, and satisfiability, including structural classifications and complexity bounds. It reports sharp examples such as foldability characterizing connected 3-colour mixing and Wilson’s classification of most 2-connected puzzle graphs, while identifying unresolved complexity questions.

  • Problem

    The central question is the computational complexity of deciding whether feasible configurations can be transformed into one another under restricted moves.

  • Method

    The survey organizes prior results using configuration graphs and reviews structural and complexity classifications for colouring, token, and satisfiability reconfiguration.

  • Results

    The surveyed results include exact structural criteria for some mixing problems and classifications ranging from P and coNP to PSPACE-complete for satisfiability connectivity.

  • Takeaways & Limitations

    Reconfiguration complexity can depend on structural properties of the underlying graph or relation set, with some cases admitting concise characterizations and others remaining computationally hard.

  • Takeaways & Limitations

    The complexity of k-Colour-Mixing for k ≥4 and k-List-Colour-Mixing for k ≥3 remains open, although structural characterizations may be possible.

Abstract

from arXiv · show

Many combinatorial problems can be formulated as "Can I transform configuration 1 into configuration 2, if certain transformations only 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 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?

1 Introduction

Reconfiguration problems ask whether feasible configurations can be connected by allowed transformations while preserving feasibility. The survey frames these questions through configuration graphs and studies their computational complexity under compact, algorithmically checkable descriptions.

  • 1 Introduction: Reconfiguration problems specify feasible configurations and transformations that change one configuration into another.Examples include the 15-puzzle, Rubik’s cube, graph colourings, and satisfying assignments.
  • 1 Introduction: The survey focuses on deciding whether transformations are possible, while also noting distance and extremal-separation questions.These additional questions include the number of steps between configurations and which configurations are furthest apart.
  • 1 Introduction: A-to-B-Path asks whether two specified configurations lie in the same component via feasible intermediate configurations.Path-between-All-Pairs instead asks whether every pair of feasible configurations can be connected in this way.
  • 1 Introduction: A configuration graph has feasible configurations as vertices and transformation pairs as edges, generally treated as undirected when transformations are reversible.This graph representation converts transformation questions into connectivity questions.
  • 1 Introduction: Instances use compact descriptions with polynomial-time tests for feasibility and for whether one feasible configuration transforms directly into another.These assumptions avoid explicitly listing all configurations or transformations.
  • 1 Introduction: Under these assumptions, both general reconfiguration problems are in PSPACE via a polynomial-space nondeterministic search.The search guesses successive configurations, checks feasibility and transformations, and replaces the current configuration while retaining polynomial space.

2 Reconfiguration of satisfiability problems

Boolean formula reconfiguration views satisfying assignments as feasible configurations and single-variable changes as transformations. The survey connects connectivity complexity to relation classes, obtaining a tight-set dichotomy for specified paths and broader classifications for global connectivity.

  • 2 Reconfiguration of satisfiability problems: For a Boolean formula ϕ with n variables, feasible configurations are satisfying assignments in {T, F}^n, and transformations change exactly one variable.The resulting configuration graph is the subgraph of the n-dimensional hypercube induced by satisfying assignments.
  • 2 Reconfiguration of satisfiability problems: CNF(S)-formulas are conjunctions of clauses built from a finite set S of logical relations, and Sat(S) asks whether such a formula is satisfiable.The survey introduces logical relations as subsets of Boolean tuples and illustrates 2-CNF and 3-CNF representations.
  • 2 Reconfiguration of satisfiability problems: Schaefer’s theorem classifies Sat(S) as polynomial-time solvable for Schaefer sets and NP-complete otherwise, while every Schaefer set is tight.Tightness is the key relation property used in the reconfiguration classification.
  • 2 Reconfiguration of satisfiability problems: st-Conn(S) asks whether two satisfying assignments are connected, whereas Conn(S) asks whether the entire solution configuration graph is connected.These are the specified-pair and all-pairs versions of satisfiability reconfiguration.
  • 2 Reconfiguration of satisfiability problems: If S is tight, st-Conn(S) is in P; otherwise it is PSPACE-complete.For Conn(S), tight sets place the problem in coNP, tight non-Schaefer sets make it coNP-complete, and other sets make it PSPACE-complete.
  • 2 Reconfiguration of satisfiability problems: Tight relations permit paths of length O(n) between connected assignments, whereas non-tight relations admit instances requiring exponentially many transformations.The exponential lower bound occurs for arbitrarily large numbers of variables.
  • 2 Reconfiguration of satisfiability problems: A proposed P classification for Conn(S) on all Schaefer sets was disproved, because some Schaefer relations yield coNP-complete connectivity.The survey notes that the conjecture remains true for particular Schaefer-set types.

3 Reconfiguration of graph colourings

The survey examines graph-colouring reconfiguration, including single-vertex and Kempe-chain transformations, with emphasis on connectivity, path questions, complexity, and structural characterisations.

  • Single-vertex recolouring: If k ≥ deg(G)+2, every graph is k-mixing and list-mixing under lists of that size; the threshold is best possible for examples including complete graphs and trees.For planar graphs, degeneracy at most 5 implies that 7-Colour-Mixing and 7-Colour-Path are trivially in P.
  • Single-vertex recolouring: Reconfiguration problems ask whether feasible colourings can be transformed through feasible intermediate colourings, either for a specified pair or for every pair.These correspond to Colour-Path and Colour-Mixing variants.
  • Single-vertex recolouring: For single-vertex recolouring, 2-Colour-Path and 2-Colour-Mixing are in P; 3-Colour-Path is in P, whereas 3-Colour-Mixing is coNP-complete.For every k ≥4, k-Colour-Path is PSPACE-complete, and for every k ≥3, k-List-Colour-Path is PSPACE-complete.
  • Single-vertex recolouring: A connected 3-colourable graph is not 3-mixing exactly when it is foldable to C3 or C6, identifying these cycles as minimal obstructions in the stated sense.Every non-bipartite 3-colourable connected graph folds to C3; the bipartite case is characterised by foldability to C6.
  • Single-vertex recolouring: 3-colouring paths require O(n^2) recolourings whenever they exist, and this bound is best possible; exponential-length sequences occur for list colourings and ordinary k-colourings in the stated ranges.The exponential lower bounds apply to list colourings for every k ≥3 and ordinary colourings for every k ≥4.
  • Kempe chain recolouring: Kempe-chain recolouring generalises single-vertex recolouring, and k-mixing implies k-Kempe-mixing, but the converse fails even for bipartite graphs.Every bipartite graph is k-Kempe-mixing for k ≥2, while bipartite graphs that are not k-mixing exist for every k ≥2.
  • Kempe chain recolouring: Every planar graph is 5-Kempe-mixing, and every 3-colourable planar graph is 4-Kempe-mixing; neither colour bound can be reduced.The results are stated as best possible in both cases.
  • Kempe chain recolouring: The 3-prism is the smallest graph known not to be 3-Kempe-mixing, because Kempe recolourings preserve the structure of its two exhibited colourings.Whether it is minimal in a broader sense or the only such graph remains unknown.

4 Moving tokens on graphs

Token reconfiguration studies when one configuration of tokens on a graph can reach another through legal slides, and how connectivity and shortest-path complexity depend on graph structure and token labels. The results range from complete connectivity characterizations to sharp transitions between polynomial-time and NP-complete shortest-sequence problems, while stability constraints can make reachability PSPACE-complete.

  • Labelled tokens without restrictions: The 15-puzzle generalizes to sliding n−1 labelled tokens on any graph, with the central question whether all token configurations are mutually reachable.The puzzle graph represents configurations as vertices and legal single-token moves as edges.
  • Labelled tokens without restrictions: Wilson’s theorem characterizes labelled-token connectivity on 2-connected graphs: cycles, bipartite graphs, and θ0 are the exceptions, with (n−2)!, two, and six components respectively.The theorem assumes n ≥3 and identifies the exceptional component counts explicitly.
  • Labelled tokens without restrictions: For general token sets, disconnectedness is characterized by graph separations, saturation, paths, cycles, bipartiteness, and specific θ0 token sets.This extends the connectivity analysis beyond the case where every token is distinct.
  • Labelled tokens without restrictions: If G is 2-connected, non-cyclic, and the total token count is at most n−2, then the corresponding puzzle graph is always connected.A further result characterizes which configurations lie in the same component, extending earlier algorithmic results.
  • Labelled tokens without restrictions: Shortest-Token-Moves-Sequence is in P when all tokens are identical, but becomes NP-complete as soon as tokens are not all identical, including one-special-token instances.The identical-token case admits polynomial-time minimum-step computation, whereas the one-special-token case is NP-complete.
  • Unlabelled Tokens with Restrictions: Adding stable-set restrictions makes token reachability PSPACE-complete for both edge-sliding moves and unrestricted jumps, even on planar graphs of maximum degree three.The unrestricted-jump formulation allows a token to move to any vacant vertex while every intermediate occupied set remains stable.
  • Unlabelled Tokens with Restrictions: NCL-Configuration-to-Edges is PSPACE-complete even under planar, degree-three, unit-or-two edge-weight, and vertex-weight-two restrictions.The task asks whether a specified edge can have its orientation reversed through feasible intermediate configurations.
  • Unlabelled Tokens with Restrictions: Other constrained reconfiguration problems can be polynomial: any minimum spanning tree can reach any other by minimum-spanning-tree exchanges, and Matching-Reconfiguration is in P.These results contrast with the PSPACE-complete stable-token problems.

5 Applications

Reconfiguration problems connect to sampling, counting, puzzles, games, frequency assignment, and robot motion. The survey emphasizes how connectivity and transformation complexity affect these applications.

  • 5.1 Sampling and counting: Glauber dynamics updates a graph colouring by randomly selecting a vertex and colour, retaining the recolouring only when propriety is preserved.Its state space consists of all k-colourings, with an arbitrary initial colouring.
  • 5.1 Sampling and counting: k-mixing is necessary for Glauber dynamics to be rapidly mixing, but stars K1,m show that it is not sufficient.Stars are k-mixing for k ≥3, yet their Glauber dynamics is not rapidly mixing for k ≤m1−ε, for fixed ε > 0.
  • 5.1 Sampling and counting: Reconfiguration problems can support almost-uniform sampling and approximate counting when their configuration graphs are connected.A Markov chain used for sampling must also be rapidly mixing to converge near its stationary distribution in polynomial time.
  • 5.2 Puzzles and games: Reconfiguration is also used to formalize one-player puzzles and two-player games involving reachable configurations under allowed moves.The survey points to prior complexity studies of puzzles and games, including classical examples such as the 15-puzzle and Sokoban.
  • 5.3 Other applications: Graph recolouring models frequency assignment, where the goal is to minimize interference while using the smallest possible frequency range.The radio spectrum is limited and demand for dependent services is growing, making efficient use increasingly important.
  • 5.3 Other applications: Robot motion illustrates that deciding reachability may be easier than determining whether a target configuration can be reached within a bounded number of steps.Sokoban reachability is PSPACE-complete, while practical motion planning also motivates step-minimization questions.

6 Open problem

The survey identifies understanding the link between reconfiguration complexity and ordinary configuration-existence problems as a fundamental open direction. Existing examples show that this relationship is subtler than transferring NP-completeness directly to PSPACE-completeness.

  • 6 Open problem: A central open problem is to connect reconfiguration complexity with the complexity of deciding whether configurations of a relevant kind exist.The survey presents this connection as more fundamental than compiling a long list of individual open problems.
  • 6 Open problem: The conjecture that Schaefer constraint languages yield polynomial-time connectivity has been disproved, illustrating that proposed links can fail.The passage cites Gopalan et al.'s conjecture about Conn(S) and notes its later disproof.
  • 6 Open problem: NP-completeness of an underlying decision problem does not by itself imply PSPACE-completeness of the corresponding reconfiguration problem.For graph colouring, connectivity of 3-colourings is in P, whereas connectivity for k-colourings is PSPACE-complete for k ≥4.
  • 6 Open problem: A subtler connection may exist for constrained labelling problems with single-object relabelling transformations, including satisfiability and graph colouring.The survey suggests that identifying such a connection could improve understanding of these complexity relationships.
Loading 1312.2816v1…