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

Matthew Johnson, Barnaby Martin, Siani Smith +3

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…