License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2019.27
URN: urn:nbn:de:0030-drops-104311
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10431/
Cohen-Addad, Vincent ;
Colin de Verdière, Éric ;
Marx, Dániel ;
de Mesmay, Arnaud
Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
Abstract
We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem.
A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus g has a cut graph of length at most a given value. We prove a time lower bound for this problem of n^{Omega(g/log g)} conditionally to ETH. In other words, the first n^{O(g)}-time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year old question of these authors.
A multiway cut of an undirected graph G with t distinguished vertices, called terminals, is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n^{Omega(sqrt{gt + g^2}/log(gt))}, conditionally to ETH, for any choice of the genus g >=0 of the graph and the number of terminals t >=4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case).
Reductions to planar problems usually involve a grid-like structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value g of the genus.
BibTeX - Entry
@InProceedings{cohenaddad_et_al:LIPIcs:2019:10431,
author = {Vincent Cohen-Addad and {\'E}ric Colin de Verdi{\`e}re and D{\'a}niel Marx and Arnaud de Mesmay},
title = {{Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {27:1--27:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-104-7},
ISSN = {1868-8969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10431},
URN = {urn:nbn:de:0030-drops-104311},
doi = {10.4230/LIPIcs.SoCG.2019.27},
annote = {Keywords: Cut graph, Multiway cut, Surface, Lower bound, Parameterized Complexity, Exponential Time Hypothesis}
}
|
Keywords: |
|
Cut graph, Multiway cut, Surface, Lower bound, Parameterized Complexity, Exponential Time Hypothesis |
|
Collection: |
|
35th International Symposium on Computational Geometry (SoCG 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
11.06.2019 |
