{"ID":5443813,"CreatedAt":"2026-07-01T02:07:11.383974684Z","UpdatedAt":"2026-07-03T15:14:29.341850669Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31815","arxiv_id":"2606.31815","title":"Token sliding independent set reconfiguration on graphs with few $P_4$'s","abstract":"We consider the INDEPENDENT SET RECONFIGURATION problem under the Token Sliding rule. Let $I$ be an independent set of a simple undirected graph $G$. Suppose that each vertex of $I$ 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$. The problem we deal is to decide if we can transform $I$ into $I'$ 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, bipartite permutation graphs, block graphs, and cographs. We present a polynomial time algorithm for the problem on $P_4$-tidy graphs and $(q,q-4)$-graphs, both families of graphs generalizing cographs.","short_abstract":"We consider the INDEPENDENT SET RECONFIGURATION problem under the Token Sliding rule. Let $I$ be an independent set of a simple undirected graph $G$. Suppose that each vertex of $I$ 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, t...","url_abs":"https://arxiv.org/abs/2606.31815","url_pdf":"https://arxiv.org/pdf/2606.31815v1","authors":"[\"Lucia Busolini\",\"Mario Valencia-Pabon\"]","published":"2026-06-30T15:28:00Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}