TY - GEN

T1 - Separator Theorem and Algorithms for Planar Hyperbolic Graphs

AU - Kisfaludi-Bak, Sándor

AU - Masarìkovà, Jana

AU - van Leeuwen, Erik Jan

AU - Walczak, Bartosz

AU - Wegrzycki, Karol

N1 - Publisher Copyright:
© Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen, Bartosz Walczak, and Karol Węgrzycki.

PY - 2024

Y1 - 2024

N2 - 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.

AB - 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.

KW - Approximation Algorithms

KW - Hyperbolic metric

KW - Planar Graphs

KW - r-Division

UR - http://www.scopus.com/inward/record.url?scp=85195476562&partnerID=8YFLogxK

U2 - 10.4230/LIPICS.SOCG.2024.67

DO - 10.4230/LIPICS.SOCG.2024.67

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 67:1-67:17

BT - 40th International Symposium on Computational Geometry, SoCG 2024

A2 - Mulzer, Wolfgang

A2 - Phillips, Jeff M.

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

ER -