Planar Multiway Cut with Terminals on Few Faces

Sukanya Pandey; Erik Jan van Leeuwen

doi:10.1137/1.9781611977073.81

Planar Multiway Cut with Terminals on Few Faces

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We consider the Edge Multiway Cut problem on planar graphs. It is known that this can be solved in time [Klein, Marx, ICALP 2012] and not in time under the Exponential Time Hypothesis [Marx, ICALP 2012], where t is the number of terminals. A generalization of this parameter is the number k of faces of the planar graph that jointly cover all terminals. For the related Steiner Tree problem, an 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 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.

Original language	English
Title of host publication	Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022
Publisher	SIAM
Pages	2032-2063
Number of pages	32
ISBN (Electronic)	978-1-61197-707-3
DOIs	https://doi.org/10.1137/1.9781611977073.81
Publication status	Published - 2022

Access to Document

10.1137/1.9781611977073.81

1.9781611977073.81Final published version, 1.38 MBLicence: Taverne

Cite this

@inproceedings{be391b35f3f444a495dedaa0b2e58e63,

title = "Planar Multiway Cut with Terminals on Few Faces",

abstract = "We consider the Edge Multiway Cut problem on planar graphs. It is known that this can be solved in time [Klein, Marx, ICALP 2012] and not in time under the Exponential Time Hypothesis [Marx, ICALP 2012], where t is the number of terminals. A generalization of this parameter is the number k of faces of the planar graph that jointly cover all terminals. For the related Steiner Tree problem, an 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 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.",

author = "Sukanya Pandey and {van Leeuwen}, {Erik Jan}",

year = "2022",

doi = "10.1137/1.9781611977073.81",

language = "English",

pages = "2032--2063",

booktitle = "Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022",

publisher = "SIAM",

}

Planar Multiway Cut with Terminals on Few Faces. / Pandey, Sukanya; van Leeuwen, Erik Jan.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022. SIAM, 2022. p. 2032-2063.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Planar Multiway Cut with Terminals on Few Faces

AU - Pandey, Sukanya

AU - van Leeuwen, Erik Jan

PY - 2022

Y1 - 2022

N2 - We consider the Edge Multiway Cut problem on planar graphs. It is known that this can be solved in time [Klein, Marx, ICALP 2012] and not in time under the Exponential Time Hypothesis [Marx, ICALP 2012], where t is the number of terminals. A generalization of this parameter is the number k of faces of the planar graph that jointly cover all terminals. For the related Steiner Tree problem, an 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 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.

AB - We consider the Edge Multiway Cut problem on planar graphs. It is known that this can be solved in time [Klein, Marx, ICALP 2012] and not in time under the Exponential Time Hypothesis [Marx, ICALP 2012], where t is the number of terminals. A generalization of this parameter is the number k of faces of the planar graph that jointly cover all terminals. For the related Steiner Tree problem, an 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 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.

U2 - 10.1137/1.9781611977073.81

DO - 10.1137/1.9781611977073.81

M3 - Conference contribution

SP - 2032

EP - 2063

BT - Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022

PB - SIAM

ER -

Planar Multiway Cut with Terminals on Few Faces

Abstract

Access to Document

Fingerprint

Cite this