Edge Multiway Cut and Node Multiway Cut are NP-complete on Subcubic Graphs

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

doi:10.48550/arXiv.2211.12203

Edge Multiway Cut and Node Multiway Cut are NP-complete on Subcubic Graphs

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

Research output: Working paper › Preprint › Academic

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.

Original language	English
Publisher	arXiv
Pages	1-13
DOIs	https://doi.org/10.48550/arXiv.2211.12203
Publication status	Published - 22 Nov 2022

Access to Document

10.48550/arXiv.2211.12203Licence: CC BY

2211.12203Submitted manuscript, 721 KBLicence: CC BY

Cite this

@techreport{b05d980e3a5943999e8b316203456464,

title = "Edge Multiway Cut and Node Multiway Cut are NP-complete on Subcubic Graphs",

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.",

author = "Johnson, {Matthew S.} and Barnaby Martin and Siani Smith and Sukanya Pandey and Dani{\"e}l Paulusma and {van Leeuwen}, {Erik Jan}",

year = "2022",

month = nov,

day = "22",

doi = "10.48550/arXiv.2211.12203",

language = "English",

pages = "1--13",

publisher = "arXiv",

type = "WorkingPaper",

institution = "arXiv",

}

TY - UNPB

T1 - Edge Multiway Cut and Node Multiway Cut are NP-complete on Subcubic Graphs

AU - Johnson, Matthew S.

AU - Martin, Barnaby

AU - Smith, Siani

AU - Pandey, Sukanya

AU - Paulusma, Daniël

AU - van Leeuwen, Erik Jan

PY - 2022/11/22

Y1 - 2022/11/22

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

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

U2 - 10.48550/arXiv.2211.12203

DO - 10.48550/arXiv.2211.12203

M3 - Preprint

SP - 1

EP - 13

BT - Edge Multiway Cut and Node Multiway Cut are NP-complete on Subcubic Graphs

PB - arXiv

ER -

Edge Multiway Cut and Node Multiway Cut are NP-complete on Subcubic Graphs

Abstract

Access to Document

Fingerprint

Cite this