Parameterized complexity of independent set reconfiguration problems

DOI10.1016/J.DAM.2020.01.022MaRDI QIDQ2192091zbMATH OpenOpenAlexFDO

Authors Takehiro Ito, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, Katsuhisa Yamanaka, Marcin Kamiński

Publication date 29 June 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2020.01.022

zbMATH Keywords

graph algorithmindependent setfixed parameter tractabilitycombinatorial reconfiguration

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Complexity of independent set reconfigurability problems
• The complexity of independent set reconfiguration on bipartite graphs
• The complexity of independent set reconfiguration on bipartite graphs
• On the complexity of distance-\(d\) independent set reconfiguration
• Parameterized extension complexity of independent set and related problems
• On the parameterized complexity of reconfiguration of connected dominating sets

Cites work

• Complexity of independent set reconfigurability problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fixed-parameter tractability of token jumping on planar graphs
• Games, puzzles, and computation
• Independent set reconfiguration in cographs and their generalizations
• Introduction to reconfiguration
• Linear-time algorithm for sliding tokens on trees
• On the Parameterized Complexity for Token Jumping on Graphs
• On the complexity of reconfiguration problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration over tree decompositions
• Reconfiguring independent sets in claw-free graphs
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Sliding token on bipartite permutation graphs
• Sliding tokens on a cactus
• The complexity of change
• The complexity of independent set reconfiguration on bipartite graphs
• Token jumping in minor-closed classes
• Token sliding on chordal graphs

Cited in

(15)

• Independent-set reconfiguration thresholds of hereditary graph classes
• Independent-set reconfiguration thresholds of hereditary graph classes
• Incremental optimization of independent sets under the reconfiguration framework
• Fixed-parameter tractability of token jumping on planar graphs
• On finding short reconfiguration sequences between independent sets
• Reconfiguration of regular induced subgraphs
• On reconfiguration graphs of independent sets under token sliding
• On girth and the parameterized complexity of token sliding and token jumping
• Complexity of independent set reconfigurability problems
• The complexity of induced tree reconfiguration problems
• The complexity of independent set reconfiguration on bipartite graphs
• Extremal independent set reconfiguration
• The complexity of independent set reconfiguration on bipartite graphs
• On the complexity of distance-\(d\) independent set reconfiguration
• On finding short reconfiguration sequences between independent sets

This page was built for publication: Parameterized complexity of independent set reconfiguration problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192091)