Shortest Reconfiguration of Sliding Tokens on a Caterpillar

DOI10.1007/978-3-319-30139-6_19zbMATH Open1475.68254arXiv1511.00243OpenAlexW2258225879MaRDI QIDQ2803826FDOQ2803826

Authors: Takeshi Yamada, Ryuhei Uehara 

Publication date: 3 May 2016

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Abstract: Suppose that we are given two independent sets I_b and I_r of a graph such that |I_b|=|I_r|, and imagine that a token is placed on each vertex in |I_b|. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I_b into I_r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. The sliding token problem is one of the reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. The reconfiguration problems tend to be PSPACE-complete in general, and some polynomial time algorithms are shown in restricted cases. Recently, the problems that aim at finding a shortest reconfiguration sequence are investigated. For the 3SAT problem, a trichotomy for the complexity of finding the shortest sequence has been shown, that is, it is in P, NP-complete, or PSPACE-complete in certain conditions. In general, even if it is polynomial time solvable to decide whether two instances are reconfigured with each other, it can be NP-complete to find a shortest sequence between them. Namely, finding a shortest sequence between two independent sets can be more difficult than the decision problem of reconfigurability between them. In this paper, we show that the problem for finding a shortest sequence between two independent sets is polynomial time solvable for some graph classes which are subclasses of the class of interval graphs. More precisely, we can find a shortest sequence between two independent sets on a graph G in polynomial time if either G is a proper interval graph, a trivially perfect graph, or a caterpillar. As far as the authors know, this is the first polynomial time algorithm for the shortest sliding token problem for a graph class that requires detours.

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

Recommendations

• Shortest reconfiguration sequence for sliding tokens on spiders
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• Dominating sets reconfiguration under token sliding
• Polynomial-time algorithm for sliding tokens on trees
• On reconfiguration graphs of independent sets under token sliding
• Sliding token on bipartite permutation graphs
• Linear-time algorithm for sliding tokens on trees
• Shortest reconfiguration of matchings
• Token sliding on chordal graphs
• On girth and the parameterized complexity of token sliding and token jumping

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Graph Classes: A Survey
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Reconfiguring independent sets in claw-free graphs
• Games, puzzles, and computation
• Complexity of independent set reconfigurability problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• On the complexity of reconfiguration problems
• The \((n^ 2-1)\)-puzzle and related relocation problems
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Reconfiguration over tree decompositions
• Linear-time algorithm for sliding tokens on trees
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Sliding token on bipartite permutation graphs
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar

Cited In (7)

• Parameterized complexity of independent set reconfiguration problems
• Introduction to reconfiguration
• Sliding tokens on a cactus
• Sliding token on bipartite permutation graphs
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• Reconfiguration of cliques in a graph
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar

This page was built for publication: Shortest Reconfiguration of Sliding Tokens on a Caterpillar

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