Planar Multiway Cut with Terminals on Few Faces CCS: Theory of computation Parameterized complexity and exact algorithms

Sukanya Pandey, Erik Jan van Leeuwen · 2025

Read Planar Multiway Cut with Terminals on Few Faces CCS: Theory of computation Parameterized complexity and exact algorithms by Sukanya Pandey, Erik Jan van Leeuwen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-23399.txt.

Description

Sukanya Pandey and Erik Jan van Leeuwen speed up a graph cutting problem when the key points cluster on few faces. Edge Multiway Cut asks for the cheapest edges whose removal splits set terminals apart. On flat graphs the known run time grows with the terminal count. Their 2025 paper swaps in a sharper measure: the number of faces that together cover all terminals. When that count is small, their method runs far faster.

The proof mixes heavy planar graph tools. Homotopy and sphere-cut splits tame the graph's shape. A global treewidth program then joins with a local Dreyfus-Wagner style one to handle crowds of terminals per face. The gain mirrors a recent leap for the Steiner Tree problem.

Catalog record

CREATORSukanya Pandey, Erik Jan van Leeuwen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE209 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-23399

Browse the full library · About the Tower of Babel