On girth and the parameterized complexity of token sliding and Token Jumping

DOI10.1007/s00453-021-00848-1OpenAlexW3117234799MaRDI QIDQ1979464

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

Publication date: 2 September 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

independent setparameterized complexitycombinatorial reconfigurationToken JumpingToken Sliding

Mathematics Subject Classification ID

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

Related Items (4)

Reconfiguration of regular induced subgraphs ⋮ Token sliding on graphs of girth five ⋮ Galactic token sliding ⋮ Token sliding on graphs of girth five

Cites Work

• Unnamed Item
• Unnamed Item
• A dichotomy theorem for circular colouring reconfiguration
• Complexity of independent set reconfigurability problems
• On the complexity of reconfiguration problems
• Reconfiguration of list edge-colorings in a graph
• Flip distance between two triangulations of a point set is NP-complete
• Token jumping in minor-closed classes
• Reconfiguration in bounded bandwidth and tree-depth
• Token sliding on chordal graphs
• Reconfiguration on sparse graphs
• Token sliding on split graphs
• Introduction to reconfiguration
• Connectedness of the graph of vertex-colourings
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• Fixed-Parameter Tractability of Token Jumping on Planar Graphs
• Polynomial-Time Algorithm for Sliding Tokens on Trees
• Vertex Cover Reconfiguration and Beyond
• Homomorphism reconfiguration via homotopy
• Reconfiguring Independent Sets in Claw-Free Graphs
• Ground State Connectivity of Local Hamiltonians
• Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
• Sliding Token on Bipartite Permutation Graphs
• The Complexity of Independent Set Reconfiguration on Bipartite Graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Parameterized Complexity of Independent Set in H-Free Graphs.
• On the Parameterized Complexity for Token Jumping on Graphs
• Parameterized Algorithms
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

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