Abstract
We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surfaceembedded 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 HarPeled [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 17year 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 gridlike 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 CohenAddad 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:127:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10431},
URN = {urn:nbn:de:0030drops104311},
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 