Linear-time algorithm for sliding tokens on trees

DOI10.1016/J.TCS.2015.07.037zbMATH Open1329.68135arXiv1406.6576OpenAlexW2169085828MaRDI QIDQ496016FDOQ496016

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)

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.

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

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

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)

Cites Work

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

Cited In (32)

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