On girth and the parameterized complexity of token sliding and token jumping

DOI10.1007/S00453-021-00848-1MaRDI QIDQ1979464zbMATH OpenOpenAlexFDO

Authors Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, Amer E. Mouawad

Publication date 2 September 2021

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.01673, https://drops.dagstuhl.de/opus/volltexte/2020/13388/

zbMATH Keywords

combinatorial reconfigurationindependent setparameterized complexityToken JumpingToken Sliding

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Recommendations

• Fixed-parameter tractability of token jumping on planar graphs
• On the Parameterized Complexity for Token Jumping on Graphs
• Token jumping in minor-closed classes
• Parameterized complexity of independent set reconfiguration problems
• Token sliding on chordal graphs

Cites work

• A dichotomy theorem for circular colouring reconfiguration
• Complexity of independent set reconfigurability problems
• Connectedness of the graph of vertex-colourings
• Fixed-parameter tractability of token jumping on planar graphs
• Flip distance between two triangulations of a point set is NP-complete
• Homomorphism reconfiguration via homotopy
• scientific article; zbMATH DE number 7765402 (Why is no real title available?)
• Introduction to reconfiguration
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On the complexity of reconfiguration problems
• On the Parameterized Complexity for Token Jumping on Graphs
• Parameterized algorithms
• Parameterized complexity of independent set in \(H\)-free graphs
• Polynomial-time algorithm for sliding tokens on trees
• 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 of list edge-colorings in a graph
• Reconfiguring independent sets in claw-free graphs
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Sliding token on bipartite permutation graphs
• The complexity of change
• The complexity of independent set reconfiguration on bipartite graphs
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Token jumping in minor-closed classes
• Token sliding on chordal graphs
• Token sliding on split graphs
• Vertex Cover Reconfiguration and Beyond

Cited in

(15)

• Reconfiguration of regular induced subgraphs
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Fixed-parameter tractability of token jumping on planar graphs
• Linear-time algorithm for sliding tokens on trees
• On the Parameterized Complexity for Token Jumping on Graphs
• Token sliding on graphs of girth five
• Galactic token sliding
• Token sliding on graphs of girth five
• Galactic token sliding
• Independent set reconfiguration in H-free graphs
• Reconfiguration using generalized token jumping
• A survey on the parameterized complexity of reconfiguration problems
• Independent set reconfiguration on directed graphs
• A simple quadratic kernel for token jumping on surfaces
• The tape reconfiguration problem and its consequences for dominating set reconfiguration

This page was built for publication: On girth and the parameterized complexity of token sliding and token jumping

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