Independent Set Reconfiguration Parameterized by Modular-Width
- PDF / 3,949,004 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 41 Downloads / 198 Views
Independent Set Reconfiguration Parameterized by Modular‑Width Rémy Belmonte1 · Tesshu Hanaka2 · Michael Lampis3 · Hirotaka Ono4 · Yota Otachi4 Received: 28 July 2019 / Accepted: 13 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACEcomplete even for graphs of bounded bandwidth. This fact rules out the tractability of parameterizations by most well-studied structural parameters as most of them generalize bandwidth. In this paper, we study the parameterization by modularwidth, which is not comparable with bandwidth. We show that the problem parameterized by modular-width is fixed-parameter tractable under all previously studied rules 𝖳𝖠𝖱 , 𝖳𝖩 , and 𝖳𝖲 . The result under 𝖳𝖠𝖱 resolves an open problem posed by Bonsma (J Graph Theory 83(2):164–195, 2016). Keywords Reconfiguration · Independent set · Modular-width
* Yota Otachi otachi@nagoya‑u.jp Rémy Belmonte [email protected] Tesshu Hanaka [email protected]‑u.ac.jp Michael Lampis [email protected] Hirotaka Ono ono@nagoya‑u.jp 1
The University of Electro-Communications, Chofu, Tokyo 182‑8585, Japan
2
Chuo University, Bunkyo‑ku, Tokyo 112‑8551, Japan
3
LAMSADE, CNRS, Université Paris-Dauphine, PSL University, 75016 Paris, France
4
Nagoya University, Nagoya 464‑8601, Japan
13
Vol.:(0123456789)
Algorithmica
1 Introduction In a reconfiguration problem, we are given an instance of a search problem together with two feasible solutions. The algorithmic task there is to decide whether one solution can be transformed to the other by a sequence of prescribed local modifications while maintaining the feasibility of intermediate states. Recently, reconfiguration versions of many search problems have been studied (see [22, 24]). Independent Set Reconfiguration is one of the most well-studied reconfiguration problems. In this problem, we are given a graph and two independent sets. Our goal is to find a sequence of independent sets that represents a step-by-step modification from one of the given independent sets to the other. There are three local modification rules studied in the literature: Token Addition and Removal ( 𝖳𝖠𝖱 ) [3, 18, 21], Token Jumping ( 𝖳𝖩 ) [4, 5, 15–17], and Token Sliding ( 𝖳𝖲 ) [1, 2, 8, 10, 13, 14, 20]. Under 𝖳𝖠𝖱 , given a threshold k, we can remove or add any vertices as long as the resultant independent set has size at least k. (When we want to specify the threshold k, we call the rule 𝖳𝖠𝖱(k) .) 𝖳𝖩 allows to swap one vertex in the current independent set with another vertex not dominated by the current independent set. 𝖳𝖲 is a restricted version of 𝖳𝖩 that additionally asks the swapped vertices to be adjacent. It is known that Independent Set Reconfiguration is PSPACE-complete under all three rules for general graphs [15], for perfect graphs [18], and for planar graphs of maximum degree 3 [13] (see [4]). For claw-free graphs, the pr
Data Loading...
