Separator Theorem and Algorithms for Planar Hyperbolic Graphs

Sándor Kisfaludi-Bak*, Jana Masaříková*, Erik Jan van Leeuwen*, Bartosz Walczak*, Karol Węgrzycki*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

5 Downloads (Pure)

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.

Original languageEnglish
Title of host publication40th International Symposium on Computational Geometry, SoCG 2024
EditorsWolfgang Mulzer, Jeff M. Phillips
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)978-3-95977-316-4
DOIs
Publication statusPublished - Jun 2024
MoE publication typeA4 Conference publication
EventInternational Symposium on Computational Geometry - Athens, Greece
Duration: 11 Jun 202414 Jun 2024
Conference number: 40
https://socg24.athenarc.gr/socg.html

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume293
ISSN (Print)1868-8969

Conference

ConferenceInternational Symposium on Computational Geometry
Abbreviated titleSoCG
Country/TerritoryGreece
CityAthens
Period11/06/202414/06/2024
Internet address

Keywords

  • Approximation Algorithms
  • Hyperbolic metric
  • Planar Graphs
  • r-Division

Fingerprint

Dive into the research topics of 'Separator Theorem and Algorithms for Planar Hyperbolic Graphs'. Together they form a unique fingerprint.

Cite this