Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs

Autor: Dániel Marx, Vincent Cohen-Addad, Éric Colin de Verdière, Arnaud de Mesmay
Přispěvatelé: Google Research [Zurich], Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Centre National de la Recherche Scientifique (CNRS), Helmholtz Center for Information Security [Saarbrücken] (CISPA), Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Institute for Computer Science and Control [Budapest] (SZTAKI), Hungarian Academy of Sciences (MTA), GIPSA - Architecture, Géométrie, Perception, Images, Gestes (GIPSA-AGPIG), Département Images et Signal (GIPSA-DIS), Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Grenoble Images Parole Signal Automatique (GIPSA-lab ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut Polytechnique de Grenoble - Grenoble Institute of Technology-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), de Mesmay, Arnaud, Wagner, Michael, Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)
Jazyk: angličtina
Rok vydání: 2021
Předmět:
Surface (mathematics)
Computational Geometry (cs.CG)
FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Structure (category theory)
Value (computer science)
Parameterized complexity
[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0102 computer and information sciences
Computational Complexity (cs.CC)
[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
01 natural sciences
Upper and lower bounds
Combinatorics
Set (abstract data type)
Artificial Intelligence
Genus (mathematics)
[MATH.MATH-GT]Mathematics [math]/Geometric Topology [math.GT]
Computer Science - Data Structures and Algorithms
Data Structures and Algorithms (cs.DS)
0101 mathematics
Computer Science::Data Structures and Algorithms
ComputingMilieux_MISCELLANEOUS
Mathematics
Exponential time hypothesis
000 Computer science
knowledge
general works
010102 general mathematics
QA75 Electronic computers. Computer science / számítástechnika
számítógéptudomány
Computer Science - Computational Complexity
[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
010201 computation theory & mathematics
Hardware and Architecture
Control and Systems Engineering
Computer Science
Computer Science - Computational Geometry
[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]
Software
Information Systems
Zdroj: Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (4), pp.1-26. ⟨10.1145/3450704⟩
SoCG 2019-35th International Symposium on Computational Geometry
SoCG 2019-35th International Symposium on Computational Geometry, Jun 2019, Portland, OR, United States
35th International Symposium on Computational Geometry (SoCG 2019)
Journal of the ACM
ISSN: 0004-5411
1557-735X
Popis: 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 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 Ω( gt + g 2 + t log ( 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.
Databáze: OpenAIRE
Externí odkaz: