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

Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publication19th Scandinavian Symposium on Algorithm Theory, SWAT 2024
EditorsHans L. Bodlaender
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Pages29:1-29:17
ISBN (Electronic)9783959773188
DOIs
Publication statusPublished - 2024

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume294
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

Fingerprint

Dive into the research topics of 'Edge Multiway Cut and Node Multiway Cut Are Hard for Planar Subcubic Graphs'. Together they form a unique fingerprint.

Cite this