Abstract
It is known that the weighted version of Edge Multiway Cut (also known as Multiterminal Cut) is NP-complete on planar graphs of maximum degree 3. In contrast, for the unweighted version, NP-completeness is only known for planar graphs of maximum degree 11. In fact, the complexity of unweighted Edge Multiway Cut was open for graphs of maximum degree 3 for over twenty years. We prove that the unweighted version is NP-complete even for planar graphs of maximum degree 3. As weighted Edge Multiway Cut is polynomial-time solvable for graphs of maximum degree at most 2, we have now closed the complexity gap. We also prove that (unweighted) Node Multiway Cut (both with and without deletable terminals) is NP-complete for planar graphs of maximum degree 3. By combining our results with known results, we can apply two meta-classifications on graph containment from the literature. This yields full dichotomies for all three problems on H-topological-minor-free graphs and, should H be finite, on H-subgraph-free graphs as well. Previously, such dichotomies were only implied for H-minor-free graphs.
Original language | English |
---|---|
Title of host publication | 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024 |
Editors | Hans L. Bodlaender |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik |
Pages | 29:1-29:17 |
ISBN (Electronic) | 9783959773188 |
DOIs | |
Publication status | Published - 2024 |
Publication series
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 294 |
ISSN (Print) | 1868-8969 |
Bibliographical note
Publisher Copyright:© Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen; licensed under Creative Commons License CC-BY 4.0.
Keywords
- complexity dichotomy
- graph containment
- multiway cut
- planar subcubic graph