On the complexity of reconfiguration problems

DOI10.1016/j.tcs.2010.12.005zbMath1207.68166WikidataQ115940836 ScholiaQ115940836MaRDI QIDQ631762

Yushi Uno, Ryuhei Uehara, Nicholas J. A. Harvey, Erik D. Demaine, Takehiro Ito, Christos H. Papadimitriou, Martha Sideris

Publication date: 14 March 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/99966

zbMATH Keywords

graph algorithm; approximation; PSPACE-complete; reachability on solution space; reconfiguration problems

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Frozen (Δ + 1)-colourings of bounded degree graphs, Reconfiguring vertex colourings of 2-trees, Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas, On k-Total Dominating Graphs, Trichotomy for the reconfiguration problem of integer linear systems, Reconfiguring spanning and induced subgraphs, Independent set reconfiguration parameterized by modular-width, A dichotomy theorem for circular colouring reconfiguration, Finding shortest paths between graph colourings, Reconfiguration of dominating sets, The complexity of rerouting shortest paths, Complexity of independent set reconfigurability problems, Approximability of the subset sum reconfiguration problem, Linear-time algorithm for sliding tokens on trees, The complexity of dominating set reconfiguration, On the parameterized complexity of reconfiguration problems, Reconfiguration of list edge-colorings in a graph, Connected \(k\)-dominating graphs, Parameterized complexity of the list coloring reconfiguration problem with graph parameters, Reconfiguring minimum dominating sets: the \(\gamma\)-graph of a tree, Reconfiguration on nowhere dense graph classes, Reconfiguration graphs of shortest paths, The packing number of the double vertex graph of the path graph, Reconfiguration in bounded bandwidth and tree-depth, Recoloring graphs via tree decompositions, Fixing improper colorings of graphs, Cut-colorings in coloring graphs, Reconfiguration on sparse graphs, Independent-set reconfiguration thresholds of hereditary graph classes, On girth and the parameterized complexity of token sliding and Token Jumping, Reconfiguring graph homomorphisms on the sphere, The \(k\)-dominating graph, Dominating sets reconfiguration under token sliding, The edge-connectivity of token graphs, Token sliding on split graphs, Distributed reconfiguration of maximal independent sets, Parameterized complexity of independent set reconfiguration problems, Dismantlability, connectedness, and mixing in relational structures, Optimal reconfiguration of optimal ladder lotteries, Reconfiguration of list \(L(2,1)\)-labelings in a graph, Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles, Using contracted solution graphs for solving reconfiguration problems, Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs, Introduction to reconfiguration, Reconfiguring dominating sets in some well-covered and other classes of graphs, Rerouting shortest paths in planar graphs, The connectivity of Boolean satisfiability: dichotomies for formulas and circuits, The connectivity of token graphs, A proof of the orbit conjecture for flipping edge-labelled triangulations, Reconfiguration of maximum-weight \(b\)-matchings in a graph, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, Reconfiguration of colorable sets in classes of perfect graphs, Complexity of Hamiltonian cycle reconfiguration, Shortest reconfiguration of sliding tokens on subclasses of interval graphs, Shortest Reconfiguration of Sliding Tokens on a Caterpillar, Reconfiguration of Steiner Trees in an Unweighted Graph, Independent Set Reconfiguration in Cographs and their Generalizations, A Reconfigurations Analogue of Brooks' Theorem and Its Consequences, Vertex Cover Reconfiguration and Beyond, Reconfiguration of Vertex Covers in a Graph, Degree-Constrained Subgraph Reconfiguration is in P, The Complexity of (List) Edge-Coloring Reconfiguration Problem, Sliding Tokens on Block Graphs, Approximability of the Subset Sum Reconfiguration Problem, An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree, Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas, The Complexity of Dominating Set Reconfiguration

Cites Work