paper

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs

arXiv:2211.12203 · doi:10.4230/LIPIcs.SWAT.2024.29

Abstract

We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree (also known as subcubic graphs). This improves on a previous degree bound of . Our NP-completeness result holds even for subcubic graphs that are planar.

Appeared in Proceedings of SWAT 2024

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs · wovepaper