CS Paper Radar

A linear upper bound on the number of moves required for independent set reconfiguration with two sliding tokens

Nived J. M., Mathew C. Francis

cs.DM math.CO ·submitted 2026-08-13 12:04 UTC · v1
theory

Abstract

We consider the problem of shifting two tokens placed on nonadjacent vertices $u,v$ of a graph $G$ on $n$ vertices to two nonadjacent vertices $u',v'$ of $G$ using a sequence of token movements. In each step, a token is moved from the vertex it is on to a neighbour of that vertex, ensuring that the tokens remain on nonadjacent vertices after this move. We answer a question of Briański, Felsner, Hodor, and Micek [``Reconfiguring Independent Sets on Interval Graphs'', MFCS 2021] by showing that if the two tokens can be moved from their initial position to their final position, then it can be done using at most $4n$ moves.

Comment
10 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Independent set reconfiguration is hard at treewidth four

cs.CC cs.DMmath.CO ·2026-11-15 ·Hussein Abbas, Haydar Hamieh, Amer E. Mouawad, Ali Slim
similarity 0.74
Abstract

Independent Set Reconfiguration asks whether one of two given independent sets of equal size can be transformed into the other by moving one token at a time while keeping the occupied vertices independent. In token sliding, a token moves along an edge. In token jumping, it may move to any unoccupied vertex. For both rules, the problem is solvable in polynomial time on trees and is PSPACE-complete on graphs of treewidth at most $c$ for some fixed constant $c$. For each rule, the smallest treewidth bound that suffices for hardness has long been open. We narrow this gap by proving that both versions are NP-hard on graphs of treewidth four.

0.22

Stable Set Reconfiguration in Dense Digraphs

cs.DM cs.CCmath.CO ·2026-10-23 ·Sarah Houdaigoui, Nacim Oijid, Matthieu Petiteau, Alexandre Vigny
similarity 0.65
Abstract

In a directed graph, a stable (or acyclic) set is a set which does not induce a directed cycle. Given a directed graph and two acyclic sets of the same size, the Acyclic-Set-Reconfiguration with Directed Token Sliding (ASR) problem asks whether one can, by iteratively replacing a vertex by an adjacent one, transform the first set into the second one, while maintaining acyclicity during the transformation. In this work, we present a study of the complexity of ASR and provide an FPT algorithm for semi-complete digraphs, when parametrized by the size of the sets being reconfigured, the directed pathwidth (or equivalently, the directed treewidth) of the instance, and a newly introduced parameter called the iteration of the reconfiguration sequence. To the best of our knowledge, the reconfiguration of stable sets has only been studied on undirected graphs, or (more recently) on sparse directed graphs.

0.28

A Polynomial-Time Algorithm for $k$-Path Vertex Cover Reconfiguration on Trees under Token Sliding

cs.DS cs.DM ·2026-10-22 ·Duc A. Hoang
similarity 0.65
Abstract

A $k$-path vertex cover ($k$-PVC) of a graph is a set of vertices meeting every path on $k$ vertices. In Token Sliding, one token occupies each vertex of a cover; a move slides one token along an edge to an unoccupied vertex, preserving the cover property. We study whether two covers of a tree are joined by such moves. The case $k=2$ admits a linear-time decision algorithm. For every integer $k\geq2$, we give an $O(kn^2)$-time decision algorithm on trees of order $n$, with $k$ part of the input. Two covers are reachable precisely when their rigid tokens, which never move, occupy the same set and every component remaining after their deletion has the same token count. The proof transforms configurations of equal size without rigid tokens into a canonical configuration built on properly rooted subtrees, whose paths on $k$ vertices pass through their roots. A rooted-subtree recurrence identifies movable candidate tokens. We also give a direct recursive construction between the supplied endpoints, returning at most $8n^2\,3^{\lceil n/2\rceil}$ slides in $O(n^{10}3^{n/2})$ time. ChatGPT 6 Pro and Claude Fable 5.1 were used to assist with developing and reviewing mathematical arguments and drafting and revising the paper. The author takes full responsibility for the correctness and content of the paper.

0.20

Independent Set Discovery on Biclique-Free Graphs Is Fixed-Parameter Tractable

cs.DS ·2026-08-19 ·Chenghua Liu, Boning Meng
similarity 0.62
Abstract

\textnormal{\textsc{Independent Set Discovery}} asks whether a configuration of $k$ tokens on distinct vertices can be transformed into an independent $k$-set by a sequence of token slides, each moving one token to an unoccupied neighbor; only the terminal configuration must be independent. \textnormal{\textsc{Independent Set Discovery}} is a central problem in solution discovery: its target is not prescribed and must be chosen together with the token movements needed to reach it. Fellows et al. proved it FPT in $k$ on every fixed bounded-degeneracy class and every nowhere-dense class, leaving the biclique-free case open. The biclique-free setting lies substantially beyond both regimes: biclique-free classes can have unbounded degeneracy and even be somewhere dense. We resolve the open problem affirmatively. Given an $n$-vertex, $m$-edge graph promised to be $K_{d,d}$-free and an initial $k$-token configuration, our deterministic algorithm computes the minimum number of slides and, in time $2^{O(dk\log k)}(n+m)^{O(1)}$, returns an optimal independent target and a shortest collision-free slide sequence or certifies that no independent target is reachable. Thus the problem is FPT in $k$ for every fixed $d$ and uniformly FPT in $k+d$. The proof combines an exact minimum-cost assignment characterization of token movement with local branching on bounded, cost-relevant \emph{cheap prefixes} of candidate lists. The method also yields an exact FPT algorithm for weighted independent transversals on $K_{d,d}$-free graphs with overlapping candidate sets, direct exact FPT algorithms for both problems on bounded-degeneracy graphs, an edge-count-sensitive XP algorithm, sharper bounds for bounded $s$-codegree and unbalanced biclique exclusion, and an exact extension to weighted movement on a separate directed graph.

0.20

Makespan Bounds for Synchronous Pebble Motion on Graphs

cs.DS ·2026-11-04 ·Lucy McManamon, Jingjin Yu
theory similarity 0.60
Abstract

We study the largest minimum makespan of labeled pebble motion on graphs under a model that permits synchronous pebble movement. While classical pebble motion on graphs allows only one pebble to move at a time, our model permits any number of pebbles to move to an adjacent vertex, provided that no two pebbles collide. At full occupancy every vertex is assigned a pebble and a legal round consists of disjoint cycle rotations. We prove a series of makespan bounds for this problem on graphs with varying structure and pebble density. For cycles with a chord, we extend a known quadratic bound at span two to every fixed span. For random cubic graphs, we convert permutation routing via matchings into legal schedules in two ways, applying cycle-cover batching at full occupancy and disjoint vacancy-delivery paths below full occupancy. For simple 3-connected planar cubic graphs, we prove a tight linear class maximum at every pebble count. We extend the results to increasing degree, common-neighbor conditions, and vertex connectivity. The results describe how graph connectivity, cycle structure, expansion, planarity, and occupancy affect worst-case routing time.

0.33

Supersaturation and reconfiguration diameter of independent transversals

cs.DM math.CO ·2026-11-16 ·Wouter Cames van Batenburg, Penny Haxell, Ross J. Kang, Ronen Wdowinski
theory similarity 0.59
Abstract · 14 pages, 1 figure

Consider the collection of independent transversals of a vertex-partitioned graph of maximum degree $Δ$. It is a classic result that when all parts have size at least $2Δ$, the collection is nonempty. Recently, it was found that if the parts have size at least $2Δ+1$, then every pair of independent transversals is connected, within the collection, by a sequence of one-vertex reconfigurations. We prove, among other results, that there are exponentially many independent transversals when the parts have size at least $2Δ$, and that the reconfiguration diameter is at most linear in the number of parts when the parts have size at least $4Δ$.

0.32

Detection and Construction of Small Blocking Sets via Critical Independent Sets and Matching Decomposition

cs.DM ·2026-10-09 ·Quanlong Niu, Riheng Jia
theory similarity 0.58
Abstract

The small blocking set detection and construction problem asks whether a given connected simple graph contains a nonempty independent set whose cardinality equals the size of its neighborhood and is strictly less than half the number of vertices, and, if so, how to construct such a set. Previous work characterized restless explorability in vertex-permuted temporal graphs using small blocking sets, but left the computational complexity of detecting their existence as an open problem. We give a polynomial-time algorithm for detection and construction. Specifically, we first compute a maximum-cardinality critical independent set and use its difference and cardinality to handle the cases that admit an immediate solution. In the remaining boundary case, where the critical difference is zero and the selected independent set contains exactly half the vertices, we establish a projection theorem using a perfect matching and neighborhood counting: the graph contains a small blocking set if and only if the selected independent set contains a nonempty proper tight subset. We then use matching contraction to translate the tight-subset condition into the absence of arcs leaving a vertex subset in an auxiliary digraph. This yields a strong-connectivity test for the existence of a small blocking set and, when one exists, a construction based on a sink strongly connected component. The result resolves the open complexity question for small blocking set detection and provides an explicit construction algorithm.

0.15

How rigid is maximum cardinality search? Stability and locality of MCS orderings under edge updates, verified in Lean

cs.DS cs.LO ·2026-11-13 ·Md Thoriqul Islam Thonmay, Gregory Morse
theorycode/data similarity 0.57
Abstract · 14 pages, 1 table. Code and proofs: https://github.com/thonmay/mcs-lean . Palomar registry: PALOMAR-2026-10-04-000009

For which sets F of edge modifications do a graph G and the modified graph share a maximum cardinality search (MCS) ordering? We prove that they do whenever, along every proper common MCS prefix, each unchosen vertex's neighbour count in the second graph exceeds its count in the first by zero or one. In particular, inserting or deleting any matching, or flipping a single edge, preserves a common ordering, and under the same hypothesis every common MCS prefix extends to a full common ordering without backtracking. Neither part of the hypothesis can simply be dropped: inserting a triangle, a P_4 or a 2P_3 shows that the +1 bound cannot be relaxed to +2, and a disjoint mixed insert/delete pair shows that the one-directional condition is needed. For the canonical ordering (smallest-index tie-breaking) under a single-edge update, an insertion can first change the ordering only strictly between the endpoints' positions, and a deletion only at the later endpoint; when no break fires, the ordering is unchanged. A boolean-adjacency executable refines the abstract probe-then-repair update. All of these results, including the four obstructions, are proved in Lean 4 over Mathlib, re-checked by independent kernel checkers, and registered in the Palomar registry. On paper we further show that the first break of an insertion is located in O((deg(v)+1) log n) time, independent of the window length. We claim no worst-case asymptotic speedup over recomputation.

0.45