Complexity of independent set reconfigurability problems
From MaRDI portal
Publication:441866
DOI10.1016/j.tcs.2012.03.004zbMath1246.05121OpenAlexW2145799305MaRDI QIDQ441866
Martin Milanič, Paul Medvedev, Marcin Kaminski
Publication date: 8 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.004
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)
Related Items (66)
Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ 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 ⋮ Invitation to combinatorial reconfiguration ⋮ Reconfiguration of regular induced subgraphs ⋮ Reconfiguration of dominating sets ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Reconfiguration on nowhere dense graph classes ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Vertex Cover Reconfiguration and Beyond ⋮ Finding Shortest Paths Between Graph Colourings ⋮ Reconfiguration of Vertex Covers in a Graph ⋮ The complexity of rerouting shortest paths ⋮ 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 ⋮ ZDD-based algorithmic framework for solving shortest reconfiguration problems ⋮ Feedback vertex set reconfiguration in planar graphs ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ On the complexity of distance-\(d\) independent set reconfiguration ⋮ Galactic token sliding ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ On reconfiguration graphs of independent sets under token sliding ⋮ Token sliding on graphs of girth five ⋮ Extremal independent set reconfiguration ⋮ Induced paths in graphs without anticomplete cycles ⋮ Transportation Problem Allowing Sending and Bringing Back ⋮ Unnamed Item ⋮ Computational complexity of jumping block puzzles ⋮ Reconfiguration of cliques in a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sliding Tokens on Block Graphs ⋮ Unnamed Item ⋮ Approximability of the subset sum reconfiguration problem ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Linear-time algorithm for sliding tokens on trees ⋮ Reconfiguration on sparse graphs ⋮ The complexity of dominating set reconfiguration ⋮ Reconfiguration of list \(L(2,1)\)-labelings in a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Reconfiguring spanning and induced subgraphs ⋮ Dominating sets reconfiguration under token sliding ⋮ Computational complexity of jumping block puzzles ⋮ 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 ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Token sliding on split graphs ⋮ Reconfiguration of Steiner Trees in an Unweighted Graph ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ The Perfect Matching Reconfiguration Problem ⋮ Distributed Reconfiguration of Maximal Independent Sets ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets
Cites Work
- Unnamed Item
- On the complexity of reconfiguration problems
- Shortest paths between shortest paths
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in bipartite graphs
- Complement reducible graphs
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Connectedness of the graph of vertex-colourings
- Relationships between nondeterministic and deterministic tape complexities
- Normal hypergraphs and the perfect graph conjecture
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Even-hole-free graphs part I: Decomposition theorem
- Shortest Paths between Shortest Paths and Independent Sets
- Even-hole-free graphs part II: Recognition algorithm
- Reconfiguration of List Edge-Colorings in a Graph
- Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
- A Linear Recognition Algorithm for Cographs
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: Complexity of independent set reconfigurability problems
