A polynomial-time approximation scheme for planar multiway cut
MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu · 2012
Given an undirected graph with edge lengths and a subset of nodes (called the terminals), a multiway cut (also called a multi-terminal cut) problem asks for a subset of edges with minimum total length and whose removal disconnects each terminal from the others. It generalizes the min st-cut problem but is NP-hard for planar graphs and APX-hard for general graphs. We give a polynomial-time approximation scheme for this problem on planar graphs. We prove the result by building a novel “spanner ” for multiway cut on planar graphs which is of independent interest.