Reconfiguration in bounded bandwidth and tree-depth
From MaRDI portal
Abstract: We show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth. The essential step is noticing the similarity to very limited string rewriting systems, whose ability to directly simulate Turing Machines is classically known. This resolves a question posed open in [Bonsma P., 2012]. On the other hand, we show that a large class of reconfiguration problems becomes tractable on graphs of bounded treedepth, and that this result is in some sense tight.
Recommendations
- Reconfiguration over tree decompositions
- On the Complexity of Reconfiguration Problems
- On the complexity of reconfiguration problems
- On the complexity of parameterized reachability in reconfigurable broadcast networks
- Reconfiguration of spanning trees with degree constraints or diameter constraints
- The complexity of induced tree reconfiguration problems
- Parameterized complexity of bandwidth on trees
Cites work
- scientific article; zbMATH DE number 3142911 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- A reconfigurations analogue of Brooks' theorem
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Approximating the bandwidth of caterpillars
- Complexity of independent set reconfigurability problems
- Face covers and the genus problem for apex graphs
- Finding paths between 3-colorings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Finding shortest paths between graph colourings
- Finite complete rewriting systems and the complexity of word problem
- Games, puzzles, and computation
- Grad and classes with bounded expansion. I: Decompositions
- Independent set reconfiguration in cographs and their generalizations
- No proof nets for MLL with units: proof equivalence in MLL is PSPACE-complete
- On maximal independent sets of vertices in claw-free graphs
- On the complexity of H-coloring
- On the complexity of reconfiguration problems
- On the solution-space geometry of random constraint satisfaction problems
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Parameterized complexity of graph constraint logic
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Reconfiguring independent sets in claw-free graphs
- Recursive unsolvability of a problem of Thue
- Relationships between nondeterministic and deterministic tape complexities
- Rerouting shortest paths in planar graphs
- SOFSEM 2005: Theory and Practice of Computer Science
- Shortest paths between shortest paths
- Solving the weighted stable set problem in claw-free graphs via decomposition
- Symmetric space-bounded computation
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- The complexity of bounded length graph recoloring and CSP reconfiguration
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The complexity of rerouting shortest paths
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Tree-depth, subgraph coloring and homomorphism bounds
- Using contracted solution graphs for solving reconfiguration problems
Cited in
(44)- Extremal independent set reconfiguration
- Reconfiguration over tree decompositions
- On girth and the parameterized complexity of token sliding and token jumping
- Using contracted solution graphs for solving reconfiguration problems
- Token sliding on split graphs
- Algorithms for Coloring Reconfiguration Under Recolorability Constraints
- Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
- Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
- On reconfigurability of target sets
- The shortest path reconfiguration problem based on relaxation of reconfiguration rules
- On the complexity of distance-\(d\) independent set reconfiguration
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Reconfiguration on nowhere dense graph classes
- Parameterized complexity of optimizing list vertex-coloring through reconfiguration
- Independent-set reconfiguration thresholds of hereditary graph classes
- Homomorphism reconfiguration via homotopy
- Games, Puzzles and Treewidth
- Reconfiguration of Spanning Trees with Many or Few Leaves
- Reconfiguration of vertex-disjoint shortest paths on graphs
- Token sliding on graphs of girth five
- Parameterized complexity of independent set reconfiguration problems
- Parameterized complexity of the list coloring reconfiguration problem with graph parameters
- Introduction to reconfiguration
- Token sliding on graphs of girth five
- The complexity of (list) edge-coloring reconfiguration problem
- Dominating sets reconfiguration under token sliding
- Invitation to combinatorial reconfiguration
- Reconfiguration of regular induced subgraphs
- On finding short reconfiguration sequences between independent sets
- Order Reconfiguration under Width Constraints
- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- Reconfiguring shortest paths in graphs
- On the complexity of distance-\(d\) independent set reconfiguration
- Reconfiguration of vertex-disjoint shortest paths on graphs
- Reconfiguration of vertex colouring and forbidden induced subgraphs
- Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
- Reconfiguration of colorable sets in classes of perfect graphs
- Recoloring some hereditary graph classes
- Incremental optimization of independent sets under the reconfiguration framework
- Decremental optimization of vertex-coloring under the reconfiguration framework
- A note on the connected game coloring number
- Reconfiguration of cliques in a graph
- The Perfect Matching Reconfiguration Problem
- On the complexity of restoring corrupted colorings
This page was built for publication: Reconfiguration in bounded bandwidth and tree-depth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1686224)
