2025/06/03 by Bousquet, Nicolas, Cranston, Daniel W.
#05C10 #05C69 #05C85 #68R10 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2506.03319
Fix a positive integer r, and a graph G that is K3,r-minor-free. Let Is and It be two independent sets in G, each of size k. We begin with a ``token'' on each vertex of Is and seek to move all tokens to It, by repeated ``token jumping'', removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size k. Given G, Is, and It, we ask whether there exists a sequence of token jumps that transforms Is into It. When k is part of the input, this problem is known to be PSPACE-complete. However, it was shown by Ito, Kamiński, and Ono (2014) to be fixed-parameter tractable. That is, when k is fixed, the problem can be solved in time polynomial in the order of G. Here we strengthen the upper bound on the running time in terms of k by showing that the problem has a kernel of size linear in k. More precisely, we transform an arbitrary input problem on a K3,r-minor-free graph into an equivalent problem on a (K3,r-minor-free) graph with order O(k). This answers positively a question of Bousquet, Mouawad, Nishimura, and Siebertz (2024) and improves the recent quadratic kernel of Cranston, Mühlenthaler, and Peyrille (2024+). For planar graphs, we further strengthen this upper bound to get a kernel of size at most 42k.