Token sliding independent set reconfiguration on block graphs

Let \(S\) be an independent set of a simple undirected graph \(G\). Suppose that each vertex of \(S\) has a token placed on it. The tokens are allowed to be moved, one at a time, by sliding along the edges of \(G\), so that after each move, the vertices having tokens always form an independent set o...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-10
Main Authors: Francis, Mathew C, Prabhakaran, Veena
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Graph theory
Graphs
Permutations
Polynomials
Reconfiguration
Sliding
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let \(S\) be an independent set of a simple undirected graph \(G\). Suppose that each vertex of \(S\) has a token placed on it. The tokens are allowed to be moved, one at a time, by sliding along the edges of \(G\), so that after each move, the vertices having tokens always form an independent set of \(G\). We would like to determine whether the tokens can be eventually brought to stay on the vertices of another independent set \(S'\) of \(G\) in this manner. In other words, we would like to decide if we can transform \(S\) into \(S'\) through a sequence of steps, each of which involves substituting a vertex in the current independent set with one of its neighbours to obtain another independent set. This problem of determining if one independent set of a graph ``is reachable'' from another independent set of it is known to be PSPACE-hard even for split graphs, planar graphs, and graphs of bounded treewidth. Polynomial time algorithms have been obtained for certain graph classes like trees, interval graphs, claw-free graphs, and bipartite permutation graphs. We present a polynomial time algorithm for the problem on block graphs, which are the graphs in which every maximal 2-connected subgraph is a clique. Our algorithm is the first generalization of the known polynomial time algorithm for trees to a larger class of graphs (note that trees form a proper subclass of block graphs).
ISSN:2331-8422