Daniël Paulusma

Edge Multiway Cut and Node Multiway Cut are Hard for Planar Subcubic Graphs

Abstract It is known that the weighted version of Edge Multiway Cut (also known as Multiterminal Cut ) is -complete on planar graphs of maximum degree 3. In contrast, for the unweighted version, -completeness is only known for planar graphs of maximum degree 11. In fact, the comp...