On the complexity of reconfiguration problems

DOI10.1016/j.tcs.2010.12.005zbMath1207.68166OpenAlexW1997048861WikidataQ115940836 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 algorithmapproximationPSPACE-completereachability on solution spacereconfiguration problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (only showing first 100 items - show all)

Connected \(k\)-dominating graphs ⋮ Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ Games, Puzzles and Treewidth ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Multistage vertex cover ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ The Complexity of Dominating Set Reconfiguration ⋮ A dichotomy theorem for circular colouring reconfiguration ⋮ TS-reconfiguration of dominating sets in circle and circular-arc graphs ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ Finding shortest paths between graph colourings ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Complexity of Hamiltonian cycle reconfiguration ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Invitation to combinatorial reconfiguration ⋮ Reconfiguration of regular induced subgraphs ⋮ Parameterized complexity of reconfiguration of atoms ⋮ Reconfiguring minimum dominating sets: the \(\gamma\)-graph of a tree ⋮ Reconfiguration of dominating sets ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Reconfiguration on nowhere dense graph classes ⋮ Reconfiguring dominating sets in some well-covered and other classes of graphs ⋮ Reconfiguration graphs of shortest paths ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Rerouting shortest paths in planar graphs ⋮ The packing number of the double vertex graph of the path graph ⋮ Vertex Cover Reconfiguration and Beyond ⋮ The connectivity of Boolean satisfiability: dichotomies for formulas and circuits ⋮ The connectivity of token graphs ⋮ Reconfiguration of Vertex Covers in a Graph ⋮ Degree-Constrained Subgraph Reconfiguration is in P ⋮ The complexity of rerouting shortest paths ⋮ A proof of the orbit conjecture for flipping edge-labelled triangulations ⋮ Distributed reconfiguration of maximal independent sets ⋮ Fixed-parameter algorithms for graph constraint logic ⋮ Token sliding on graphs of girth five ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Recoloring graphs via tree decompositions ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Reconfiguring (non-spanning) arborescences ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ Fixing improper colorings of graphs ⋮ Reconfiguring directed trees in a digraph ⋮ Decremental optimization of vertex-coloring under the reconfiguration framework ⋮ Computational complexity of jumping block puzzles ⋮ Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs ⋮ Complexity of independent set reconfigurability problems ⋮ Reconfiguration of cliques in a graph ⋮ The Complexity of (List) Edge-Coloring Reconfiguration Problem ⋮ Sliding Tokens on Block Graphs ⋮ Unnamed Item ⋮ Dismantlability, connectedness, and mixing in relational structures ⋮ Optimal reconfiguration of optimal ladder lotteries ⋮ Cut-colorings in coloring graphs ⋮ Reconfiguration of Spanning Trees with Many or Few Leaves ⋮ Approximability of the subset sum reconfiguration problem ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Linear-time algorithm for sliding tokens on trees ⋮ Approximability of the Subset Sum Reconfiguration Problem ⋮ An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Reconfiguration on sparse graphs ⋮ The complexity of dominating set reconfiguration ⋮ Reconfiguration of list \(L(2,1)\)-labelings in a graph ⋮ On the parameterized complexity of reconfiguration problems ⋮ Unnamed Item ⋮ The \(k\)-dominating graph ⋮ Reconfiguration of list edge-colorings in a graph ⋮ Unnamed Item ⋮ Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles ⋮ On k-Total Dominating Graphs ⋮ Reconfiguring spanning and induced subgraphs ⋮ Dominating sets reconfiguration under token sliding ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ Incremental optimization of independent sets under the reconfiguration framework ⋮ The edge-connectivity of token graphs ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Token sliding on split graphs ⋮ Reconfiguring vertex colourings of 2-trees ⋮ Reconfiguration of Steiner Trees in an Unweighted Graph ⋮ Dismantlability, Connectedness, and Mixing in Relational Structures ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ The Perfect Matching Reconfiguration Problem ⋮ Distributed Reconfiguration of Maximal Independent Sets ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Frozen (Δ + 1)-colourings of bounded degree graphs ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ Irredundance graphs ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs ⋮ Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets ⋮ Complexity of Coloring Reconfiguration under Recolorability Constraints ⋮ Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs ⋮ On the Connectivity of Token Graphs of Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Approximability of partitioning graphs with supply and demand
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration of List Edge-Colorings in a Graph
• On the Complexity of Reconfiguration Problems
• The complexity of satisfiability problems
• Some optimal inapproximability results
• PARTITIONING TREES OF SUPPLY AND DEMAND
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: On the complexity of reconfiguration problems