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
| CREATOR | Sukanya Pandey, Erik Jan van Leeuwen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 209 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-23399