TY - GEN

T1 - Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs

AU - Johnson, Matthew

AU - Martin, Barnaby

AU - Pandey, Sukanya

AU - Paulusma, Daniël

AU - Smith, Siani

AU - van Leeuwen, Erik Jan

N1 - 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.

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

KW - complexity dichotomy

KW - graph containment

KW - multiway cut

KW - planar subcubic graph

UR - http://www.scopus.com/inward/record.url?scp=85195366268&partnerID=8YFLogxK

U2 - 10.4230/LIPICS.SWAT.2024.29

DO - 10.4230/LIPICS.SWAT.2024.29

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 29:1-29:17

BT - 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024

A2 - Bodlaender, Hans L.

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

ER -