Planar Multiway Cut with Terminals on Few Faces

ACM Transactions on Algorithms, vol. 22, pp. 1–60

Abstract

We consider the Edge Multiway Cut problem on planar graphs. It is known that this can be solved in \(n^{{O}(\sqrt{t})}\) time (Klein and Marx) and not in \(n^{o(\sqrt{t})}\) time under the Exponential Time Hypothesis (Marx), where \( t \) is the number of terminals. A stronger parameter is the number \( k \) of faces of the planar graph that jointly cover all terminals. For the related Steiner Tree problem, an \(n^{{O}(\sqrt{k})}\) 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 \(n^{{O}(\sqrt{k})}\) 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.

Authors 2

1. Sukanya Pandey Aachen Department of Computer Science Dept. Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Aachen, Germany

   Dept. Computer Science, RWTH Aachen, Germany

2. Erik Jan van Leeuwen

   Utrecht University

   Affiliation as printed

   Department of Information and Computing Sciences, Utrecht University, Utrecht, Netherlands

   Dept. Information and Computing Sciences, Utrecht University, The Netherlands