Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs

Johnson, Matthew; Martin, Barnaby; Pandey, Sukanya; Paulusma, Daniel; Smith, Siani; van Leeuwen, Erik Jan

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.

Citation

Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, June). Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. Presented at SWAT 2024, Helsinki, Finland

• Presentation Conference Type: Conference Paper (published)
• Conference Name: SWAT 2024
• Start Date: Jun 12, 2024
• End Date: Dec 14, 2024
• Acceptance Date: Apr 17, 2024
• Online Publication Date: May 31, 2024
• Publication Date: May 31, 2024
• Deposit Date: Dec 27, 2024
• Publicly Available Date: Jan 3, 2025
• Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
• Peer Reviewed: Peer Reviewed
• Volume: 294
• Pages: 29:1-29:17
• Series Title: Leibniz International Proceedings in Informatics (LIPIcs)
• Series ISSN: 1868-8969
• Book Title: 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
• ISBN: 9783959773188
• DOI: https://doi.org/10.4230/LIPIcs.SWAT.2024.29
• Public URL: https://durham-repository.worktribe.com/output/3229786