Shortest Reconfiguration of Sliding Tokens on a Caterpillar

DOI10.1007/978-3-319-30139-6_19MaRDI QIDQ2803826zbMATH OpenOpenAlexFDO

Authors Takeshi Yamada, Ryuhei Uehara

Publication date 3 May 2016

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

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

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)

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.

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

Cites work

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

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)