On the parameterized complexity of reconfiguration problems

DOI10.1007/s00453-016-0159-2zbMath1360.68516arXiv1308.2409OpenAlexW1513274608MaRDI QIDQ527426

Akira Suzuki, Narges Simjour, Naomi Nishimura, Amer E. Mouawad, Venkatesh Raman

Publication date: 11 May 2017

Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.2409

zbMATH Keywords

solution spacevertex coverparameterized complexityreconfigurationhitting set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (44)

Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ 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 ⋮ 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 ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Rerouting shortest paths in planar graphs ⋮ Computing the flip distance between triangulations ⋮ Vertex Cover Reconfiguration and Beyond ⋮ Finding Shortest Paths Between Graph Colourings ⋮ Reconfiguration of Vertex Covers in a Graph ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ Reconfiguration of cliques in a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs ⋮ Linear-time algorithm for sliding tokens on trees ⋮ Reconfiguration on sparse graphs ⋮ Linear transformations between dominating sets in the TAR-model ⋮ The complexity of dominating set reconfiguration ⋮ Incremental problems in the parameterized complexity setting ⋮ Unnamed Item ⋮ 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 ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Token sliding on split graphs ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ Reconfiguration graphs for dominating sets ⋮ Kernelization of Whitney Switches ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs ⋮ Introduction to reconfiguration ⋮ Kernelization of Whitney Switches ⋮ On reconfigurability of target sets ⋮ Complexity of Coloring Reconfiguration under Recolorability Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconfiguration of dominating sets
• Solving min ones 2-SAT as fast as vertex cover
• Local search: is brute-force avoidable?
• On the complexity of reconfiguration problems
• Reconfiguration of list edge-colorings in a graph
• Shortest paths between shortest paths
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• The node-deletion problem for hereditary properties is NP-complete
• Which problems have strongly exponential complexity?
• Reconfiguration on sparse graphs
• Parameterized complexity of finding subgraphs with hereditary properties.
• The \(k\)-dominating graph
• Parametrized complexity theory.
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs
• The complexity of change
• The Complexity of Rerouting Shortest Paths
• Fixed-Parameter Tractability of Token Jumping on Planar Graphs
• Vertex Cover Reconfiguration and Beyond
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Finding Shortest Paths Between Graph Colourings
• Reconfiguration over Tree Decompositions
• Finding paths between 3-colorings
• Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
• The Complexity of Dominating Set Reconfiguration
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• A Cubic Kernel for Feedback Vertex Set
• On the Parameterized Complexity for Token Jumping on Graphs
• Parameterized Algorithms
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• On the complexity of \(k\)-SAT

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