2026-10-02T08:24:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25508 2026-09-23T23:42:12Z ddc:004 open_access

A Linear Kernel for Independent Set Reconfiguration in Planar Graphs Bousquet, Nicolas Cranston, Daniel W. Reconfiguration Independent Set Kernel Planar graphs Fix a positive integer r, and a graph G that is K_{3,r}-minor-free. Let I_s and I_t be two independent sets in G, each of size k. We begin with a "token" on each vertex of I_s and seek to move all tokens to I_t, 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, I_s, and I_t, we ask whether there exists a sequence of token jumps that transforms I_s into I_t. When k is part of the input, this problem is known to be PSPACE-complete. But it was shown by Ito, Kamiński, and Ono [Ito et al., 2014] to be fixed-parameter tractable. That is, the problem can be solved in time f(k)⋅ P(n), for some function f and polynomial P, where n denotes 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 K_{3,r}-minor-free graph (for some fixed positive integer r) into an equivalent problem on a (K_{3,r}-minor-free) graph with order O(k). This answers positively a question of Bousquet, Mouawad, Nishimura, and Siebertz [Nicolas Bousquet et al., 2022] and improves the recent quadratic kernel of Cranston, Mühlenthaler, and Peyrille [Daniel W. Cranston et al., 2024]. For planar graphs, we further strengthen this upper bound to get a kernel of size at most 42k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Bousquet and Daniel W. Cranston 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.19 urn:nbn:de:0030-drops-255081 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.19 eng https://creativecommons.org/licenses/by/4.0/legalcode