Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913471527911424 |
|---|---|
| author | Johnson, Matthew Martin, Barnaby Smith, Siani Pandey, Sukanya Paulusma, Daniel van Leeuwen, Erik Jan |
| author_facet | Johnson, Matthew Martin, Barnaby Smith, Siani Pandey, Sukanya Paulusma, Daniel van Leeuwen, Erik Jan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_12203 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs Johnson, Matthew Martin, Barnaby Smith, Siani Pandey, Sukanya Paulusma, Daniel van Leeuwen, Erik Jan Computational Complexity Discrete Mathematics Data Structures and Algorithms 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. |
| title | Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2211.12203 |