Planar Multiway Cut with Terminals on Few Faces
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911029441593344 |
|---|---|
| author | Pandey, Sukanya van Leeuwen, Erik Jan |
| author_facet | Pandey, Sukanya van Leeuwen, Erik Jan |
| contents | We consider the \textsc{Edge Multiway Cut} problem on planar graphs. It is known that this can be solved in $n^{O(\sqrt{t})}$ time [Klein, Marx, ICALP 2012] and not in $n^{o(\sqrt{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(\sqrt{k})}$ time algorithm was recently shown [Kisfaludi-Bak et al., SODA 2019]. By a completely different approach, we prove in this paper that \textsc{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23399 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Planar Multiway Cut with Terminals on Few Faces Pandey, Sukanya van Leeuwen, Erik Jan Data Structures and Algorithms F.2.0 We consider the \textsc{Edge Multiway Cut} problem on planar graphs. It is known that this can be solved in $n^{O(\sqrt{t})}$ time [Klein, Marx, ICALP 2012] and not in $n^{o(\sqrt{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(\sqrt{k})}$ time algorithm was recently shown [Kisfaludi-Bak et al., SODA 2019]. By a completely different approach, we prove in this paper that \textsc{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. |
| title | Planar Multiway Cut with Terminals on Few Faces |
| topic | Data Structures and Algorithms F.2.0 |
| url | https://arxiv.org/abs/2506.23399 |