Planar Multiway Cut with Terminals on Few Faces

2025/06/29 by Pandey, Sukanya, van Leeuwen, Erik Jan
#Data Structures and Algorithms (cs.DS) #F.2.0 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2506.23399

Abstract

We consider the Edge Multiway Cut problem on planar graphs. It is known that this can be solved in n^O(√(t)) time [Klein, Marx, ICALP 2012] and not in n^o(√(t)) time under the Exponential Time Hypothesis [Marx, ICALP 2012], 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 \sc Steiner Tree problem, an n^O(√(k)) 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 n^O(√(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.

Citations

• Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width
• Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
• Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
• Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
• An FPT algorithm for planar multicuts with sources and sinks on the\n outer face
• Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
• On Multiway Cut parameterized above lower bounds
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth
• Asymptotic enumeration and limit laws of planar graphs
• Efficient Planarity Testing

Related

• Algorithms for Cut Problems on Trees
• Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
• Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals
• A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs with a Fixed Number of Terminals
• A polynomial-time algorithm for planar multicuts with few source-sink pairs