Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
- 14 July 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (4), 1-26
- https://doi.org/10.1145/3450704
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Ω(g log g) conditionally to the ETH. In other words, the first nO(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Ω(gt+ g2+tlog (g+t)), conditionally to the 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.Keywords
Funding Information
- French ANR project (ANR-18-CE40-0004-01 (FOCAL), ANR-17-CE40-0033 (SoS), ANR-19-CE40-0014 (MIN-MAX), ANR-16-CE40-0009-01 (GATO))
- ERC Consolidator Grant SYSTEMATICGRAPH (725978)
- CNRS PEPS project COMP3D
This publication has 26 references indexed in Scilit:
- On tree width, bramble size, and expansionJournal of Combinatorial Theory, Series B, 2009
- Genus characterizes the complexity of certain graph problems: Some tight resultsJournal of Computer and System Sciences, 2007
- The complexity of homomorphism and constraint satisfaction problems seen from the other sideJournal of the ACM, 2007
- Expander graphs and their applicationsBulletin of the American Mathematical Society, 2006
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphsJournal of the ACM, 2005
- Removing excess topology from isosurfacesACM Transactions on Graphics, 2004
- Optimally Cutting a Surface into a DiskDiscrete & Computational Geometry, 2004
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary SurfaceSIAM Journal on Discrete Mathematics, 1999
- The Complexity of Multiterminal CutsSIAM Journal on Computing, 1994