Linear-time algorithm for sliding tokens on trees

DOI10.1016/J.TCS.2015.07.037MaRDI QIDQ496016zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada

Publication date 16 September 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

treegraph algorithmindependent setcombinatorial reconfigurationsliding token

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) 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. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between $I_b$ and $I_r$ whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length.

Recommendations

• Polynomial-time algorithm for sliding tokens on trees
• Linear-time algorithms for encoding trees as sequences of node labels
• On girth and the parameterized complexity of token sliding and token jumping
• scientific article; zbMATH DE number 7765402
• Token sliding on chordal graphs
• Token sliding on split graphs
• Token sliding on split graphs
• A linear-time algorithm for the generation of trees
• scientific article; zbMATH DE number 4173000
• Linear-time period computation of a string with suffix trees

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Approximability of the subset sum reconfiguration problem
• Complexity of independent set reconfigurability problems
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Games, puzzles, and computation
• Independent set reconfiguration in cographs
• On the Parameterized Complexity for Token Jumping on Graphs
• On the complexity of reconfiguration problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Polynomial-time algorithm for sliding tokens on trees
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• Reconfiguration of list edge-colorings in a graph
• Reconfiguration over tree decompositions
• Reconfiguring independent sets in claw-free graphs
• Shortest paths between shortest paths
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The complexity of rerouting shortest paths

Cited in

(32)

• Distributed reconfiguration of maximal independent sets
• Sliding token on bipartite permutation graphs
• Independent-set reconfiguration thresholds of hereditary graph classes
• Reconfiguration of Colorable Sets in Classes of Perfect Graphs
• Parameterized complexity of independent set reconfiguration problems
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• The Perfect Matching Reconfiguration Problem
• Polynomial-time algorithm for sliding tokens on trees
• Reconfiguration of maximum-weight \(b\)-matchings in a graph
• On reconfiguration graphs of independent sets under token sliding
• Distributed Reconfiguration of Maximal Independent Sets
• On reconfigurability of target sets
• Token sliding on split graphs
• On the complexity of distance-\(d\) independent set reconfiguration
• Reconfiguration of connected graph partitions
• Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs
• Complexity of coloring reconfiguration under recolorability constraints
• Sliding tokens on block graphs
• Token sliding on split graphs
• The complexity of (list) edge-coloring reconfiguration problem
• Reconfiguration of colorable sets in classes of perfect graphs
• Complexity of token swapping and its variants
• Computational complexity of puzzles and related topics
• Sliding tokens on a cactus
• The complexity of dominating set reconfiguration
• Token sliding on chordal graphs
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• Introduction to reconfiguration
• Extremal independent set reconfiguration
• On the complexity of distance-\(d\) independent set reconfiguration
• Galactic token sliding
• Reconfiguration of Steiner trees in an unweighted graph

This page was built for publication: Linear-time algorithm for sliding tokens on trees

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