Token sliding on graphs of girth five

DOI10.1007/978-3-031-15914-5_5MaRDI QIDQ6043182zbMATH OpenOpenAlexFDO

Authors Valentin Bartier, Nicolas Bousquet, Jihad Hanna, Amer E. Mouawad, Sebastian Siebertz

Publication date 5 May 2023

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial reconfigurationgirthindependent setparameterized complexitytoken sliding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: In the Token Sliding problem we are given a graph $G$ and two independent sets $I_s$ and $I_t$ in $G$ of size $kgeq1$. The goal is to decide whether there exists a sequence $langle{I}_1,I_2,ldots,I_{e}llangle$ of independent sets such that for all $iin1,ldots,ell$ the set $I_i$ is an independent set of size $k$, $I_1=I_s$, $I_{e}ll=I_t$ and $I_{i}riangle{I}_{i+1}=u,vinE(G)$. Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the problem asks whether there exists a sequence of independent sets that transforms $I_s$ into $I_t$ where at each step we are allowed to slide one token from a vertex to a neighboring vertex. In this paper, we focus on the parameterized complexity of Token Sliding parameterized by $k$. As shown by Bartier et al., the problem is W[1]-hard on graphs of girth four or less, and the authors posed the question of whether there exists a constant $pgeq5$ such that the problem becomes fixed-parameter tractable on graphs of girth at least $p$. We answer their question positively and prove that the problem is indeed fixed-parameter tractable on graphs of girth five or more, which establishes a full classification of the tractability of Token Sliding parameterized by the number of tokens based on the girth of the input graph.

Cites work

• A dichotomy theorem for circular colouring reconfiguration
• Complexity of independent set reconfigurability problems
• Connectedness of the graph of vertex-colourings
• Flip distance between two triangulations of a point set is NP-complete
• Homomorphism reconfiguration via homotopy
• Introduction to reconfiguration
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On girth and the parameterized complexity of token sliding and token jumping
• On the complexity of reconfiguration problems
• On the Parameterized Complexity for Token Jumping on Graphs
• 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
• Token sliding on chordal graphs
• Token sliding on split graphs

Cited in

(2)

• Token sliding on split graphs
• A survey on the parameterized complexity of reconfiguration problems

This page was built for publication: Token sliding on graphs of girth five

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