Back to Search
Start Over
Independent Set Reconfiguration Parameterized by Modular-Width.
- Source :
- Algorithmica; Sep2020, Vol. 82 Issue 9, p2586-2605, 20p
- Publication Year :
- 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 PSPACE-complete 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 modular-width, which is not comparable with bandwidth. We show that the problem parameterized by modular-width is fixed-parameter tractable under all previously studied rules TAR , TJ , and TS . The result under TAR resolves an open problem posed by Bonsma (J Graph Theory 83(2):164–195, 2016). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 82
- Issue :
- 9
- Database :
- Complementary Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 145348155
- Full Text :
- https://doi.org/10.1007/s00453-020-00700-y