Edge multiway cut and node multiway cut are hard for planar subcubic graphs

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

Full description

Saved in:
Bibliographic Details
Main Authors: Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, Erik Jan van Leeuwen
Format: Default Conference proceeding
Published: 2024
Subjects:
Information and computing sciences
Multiway cut
Planar subcubic graph
Complexity dichotomy
Graph containment
Online Access:https://hdl.handle.net/2134/28429271.v1
Tags: Add Tag
No Tags, Be the first to tag this record!

Similar Items