Planar Multiway Cut with Terminals on Few Faces

Abstract

We consider the Edge Multiway Cut problem on planar graphs. It is known that this can be solved in time (Klein and Marx) and not in time under the Exponential Time Hypothesis (Marx), where is the number of terminals. A stronger parameter is the number of faces of the planar graph that jointly cover all terminals. For the related Steiner Tree problem, an time algorithm was recently shown (Kisfaludi-Bak et al.). By a completely different approach, we prove in this article that Edge Multiway Cut can be solved in time as well. Our approach employs several major concepts on planar graphs, including homotopy and sphere-cut decomposition. We also mix a global treewidth dynamic program with a Dreyfus-Wagner style dynamic program to locally deal with large numbers of terminals.