Edge Multiway Cut and Node Multiway Cut are NP-complete on Subcubic Graphs
Publication date
2022-11-22
Authors
Johnson, Matthew S.
Martin, Barnaby
Smith, Siani
Pandey, Sukanya
Paulusma, Daniël
van Leeuwen, Erik Jan
Editors
Advisors
Supervisors
Document Type
/dk/atira/pure/researchoutput/researchoutputtypes/workingpaper/preprint
Metadata
Show full item recordCollections
License
cc_by
Abstract
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree 3 (also known as subcubic graphs). This improves on a previous degree bound of 11. Our NP-completeness result holds even for subcubic graphs that are planar.
Keywords
Citation
Johnson, M S, Martin, B, Smith, S, Pandey, S, Paulusma, D & van Leeuwen, E J 2022 'Edge Multiway Cut and Node Multiway Cut are NP-complete on Subcubic Graphs' arXiv, pp. 1-13. https://doi.org/10.48550/arXiv.2211.12203