Independent Set Reconfiguration Parameterized by Modular-Width
| Autor: | Yota Otachi, Michael Lampis, Tesshu Hanaka, Rémy Belmonte, Hirotaka Ono |
|---|---|
| Přispěvatelé: | autre, AUTRES, Chuo University (Chuo University), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematical Informatics, The University of Tokyo (UTokyo), Kumamoto Gakuen University, Gakuen University, University of Electro-Communications [Tokyo] (UEC), Nagoya University |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science Open problem Independent set Parameterized complexity 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Bandwidth (computing) [INFO]Computer Science [cs] Data Structures and Algorithms (cs.DS) ComputingMilieux_MISCELLANEOUS Mathematics Discrete mathematics business.industry Applied Mathematics Control reconfiguration Modular design Modular-width Computer Science Applications 010201 computation theory & mathematics Bounded function Theory of computation Reconfiguration 020201 artificial intelligence & image processing business |
| Zdroj: | Graph-Theoretic Concepts in Computer Science, Revised Papers 45th International Workshop on Graph-Theoretic Concepts in Computer Science 45th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2019, Vall de Núria, Spain. pp.285-297, ⟨10.1007/978-3-030-30786-8_22⟩ Algorithmica Algorithmica, Springer Verlag, 2020, 82 (9), pp.2586-2605. ⟨10.1007/s00453-020-00700-y⟩ Graph-Theoretic Concepts in Computer Science ISBN: 9783030307851 WG |
| ISSN: | 0178-4617 1432-0541 |
| DOI: | 10.48550/arxiv.1905.00340 |
| Popis: | 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 [WG 2014, JGT 2016]. Comment: 14 pages, 1 figure, WG 2019 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink