Back to Search
Start Over
Independent Set Reconfiguration Parameterized by Modular-Width
- Source :
- 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
- Publication Year :
- 2019
- Publisher :
- arXiv, 2019.
-
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 [WG 2014, JGT 2016].<br />Comment: 14 pages, 1 figure, WG 2019
- Subjects :
- 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
Subjects
Details
- ISBN :
- 978-3-030-30785-1
- ISSN :
- 01784617 and 14320541
- ISBNs :
- 9783030307851
- Database :
- OpenAIRE
- Journal :
- 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
- Accession number :
- edsair.doi.dedup.....19ab4ba3fd4bf040b550405de7740c53
- Full Text :
- https://doi.org/10.48550/arxiv.1905.00340