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, Marx, ICALP 2012] and not in time under the Exponential Time Hypothesis [Marx, ICALP 2012], where t is the number of terminals. A generalization of this parameter is the number k 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., SODA 2019]. By a completely different approach, we prove in this paper 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.