Separator Theorem and Algorithms for Planar Hyperbolic Graphs
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
40th International Symposium on Computational Geometry, SoCG 2024, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 293
Abstract
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on planar graphs and their relation to treewidth, we initiate the study of planar graphs of bounded hyperbolicity. Our main technical contribution is a novel balanced separator theorem for planar δ-hyperbolic graphs that is substantially stronger than the classic planar separator theorem. For any fixed δ ≽ 0, we can find a small balanced separator that induces either a single geodesic (shortest) path or a single geodesic cycle in the graph. An important advantage of our separator is that the union of our separator (vertex set Z) with any subset of the connected components of G− Z induces again a planar δ-hyperbolic graph, which would not be guaranteed with an arbitrary separator. Our construction runs in near-linear time and guarantees that the size of the separator is poly(δ) · log n. As an application of our separator theorem and its strong properties, we obtain two novel approximation schemes on planar δ-hyperbolic graphs. We prove that both Maximum Independent Set and the Traveling Salesperson problem have a near-linear time FPTAS for any constant δ, running in npolylog(n) · 2O(δ2) · ε−O(δ) time. We also show that our approximation scheme for Maximum Independent Set has essentially the best possible running time under the Exponential Time Hypothesis (ETH). This immediately follows from our third contribution: we prove that Maximum Independent Set has no no(δ)-time algorithm on planar δ-hyperbolic graphs, unless ETH fails.Description
Publisher Copyright: © Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen, Bartosz Walczak, and Karol Węgrzycki.
Other note
Citation
Kisfaludi-Bak, S, Masaříková, J, van Leeuwen, E J, Walczak, B & Węgrzycki, K 2024, Separator Theorem and Algorithms for Planar Hyperbolic Graphs. in W Mulzer & J M Phillips (eds), 40th International Symposium on Computational Geometry, SoCG 2024., 67, Leibniz International Proceedings in Informatics, LIPIcs, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Computational Geometry, Athens, Greece, 11/06/2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.67