Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs

arXiv1705.00429MaRDI QIDQ6286124FDOQ6286124

Authors: Duc A. Hoang, Ryuhei Uehara 

Publication date: 1 May 2017

Abstract: Given two independent sets $I,J$ of a graph $G$, and imagine that a token (coin) is placed at each vertex of $I$. The Sliding Token problem asks if one could transform $I$ to $J$ via a sequence of elementary steps, where each step requires sliding a token from one vertex to one of its neighbors so that the resulting set of vertices where tokens are placed remains independent. This problem is $mathsfPSPACE$-complete even for planar graphs of maximum degree $3$ and bounded-treewidth. In this paper, we show that Sliding Token can be solved efficiently for cactus graphs and block graphs, and give upper bounds on the length of a transformation sequence between any two independent sets of these graph classes. Our algorithms are designed based on two main observations. First, all structures that forbid the existence of a sequence of token slidings between $I$ and $J$, if exist, can be found in polynomial time. A sufficient condition for determining no-instances can be easily derived using this characterization. Second, without such forbidden structures, a sequence of token slidings between $I$ and $J$ does exist. In this case, one can indeed transform $I$ to $J$ (and vice versa) using a polynomial number of token-slides.

This page was built for publication: Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs

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