(2021) Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs.
|
Text
3450704.pdf Download (750kB) | Preview |
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.
| Item Type: | Article |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Depositing User: | Dániel Marx |
| Date Deposited: | 29 Apr 2022 08:44 |
| Last Modified: | 29 Apr 2022 09:37 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3625 |
Actions
Actions (login required)
 |
View Item |