DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2024.36

Path-Reporting Distance Oracles with Linear Size

Authors: Ofer Neiman and Idan Shabat

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract

Given an undirected weighted graph, an (approximate) distance oracle is a data structure that can (approximately) answer distance queries. A Path-Reporting Distance Oracle, or PRDO, is a distance oracle that must also return a path between the queried vertices. Given a graph on n vertices and an integer parameter k ≥ 1, Thorup and Zwick [M. Thorup and U. Zwick, 2001] showed a PRDO with stretch 2k-1, size O(k⋅n^{1+1/k}) and query time O(k) (for the query time of PRDOs, we omit the time needed to report the path itself). Subsequent works [Mendel and Naor, 2007; Shiri Chechik, 2014; Shiri Chechik, 2015] improved the size to O(n^{1+1/k}) and the query time to O(1). However, these improvements produce distance oracles which are not path-reporting. Several other works [Michael Elkin et al., 2016; Michael Elkin and Seth Pettie, 2016] focused on small size PRDO for general graphs, but all known results on distance oracles with linear size suffer from polynomial stretch, polynomial query time, or not being path-reporting. In this paper we devise the first linear size PRDO with poly-logarithmic stretch and low query time O(log log n). More generally, for any integer k ≥ 1, we obtain a PRDO with stretch at most O(k^4.82), size O(n^{1+1/k}), and query time O(log k). In addition, we can make the size of our PRDO as small as n+o(n), at the cost of increasing the query time to poly-logarithmic. For unweighted graphs, we improve the stretch to O(k²). We also consider pairwise PRDO, which is a PRDO that is only required to answer queries from a given set of pairs P. An exact PRDO of size O(n+|P|²) and constant query time was provided in [Michael Elkin and Seth Pettie, 2016]. In this work we dramatically improve the size, at the cost of slightly increasing the stretch. Specifically, given any ε > 0, we devise a pairwise PRDO with stretch 1+ε, constant query time, and near optimal size n^o(1)⋅ (n+|P|).

Cite as

Ofer Neiman and Idan Shabat. Path-Reporting Distance Oracles with Linear Size. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{neiman_et_al:LIPIcs.SWAT.2024.36,
  author =	{Neiman, Ofer and Shabat, Idan},
  title =	{{Path-Reporting Distance Oracles with Linear Size}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.36},
  URN =		{urn:nbn:de:0030-drops-200760},
  doi =		{10.4230/LIPIcs.SWAT.2024.36},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, Distance Oracles}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2024.83

On the Size Overhead of Pairwise Spanners

Authors: Ofer Neiman and Idan Shabat

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract

Given an undirected possibly weighted n-vertex graph G = (V,E) and a set 𝒫 ⊆ V² of pairs, a subgraph S = (V,E') is called a P-pairwise α-spanner of G, if for every pair (u,v) ∈ 𝒫 we have d_S(u,v) ≤ α⋅ d_G(u,v). The parameter α is called the stretch of the spanner, and its size overhead is define as |E'|/|P|. A surprising connection was recently discussed between the additive stretch of (1+ε,β)-spanners, to the hopbound of (1+ε,β)-hopsets. A long sequence of works showed that if the spanner/hopset has size ≈ n^{1+1/k} for some parameter k ≥ 1, then β≈(1/ε)^{log k}. In this paper we establish a new connection to the size overhead of pairwise spanners. In particular, we show that if |P|≈ n^{1+1/k}, then a P-pairwise (1+ε)-spanner must have size at least β⋅ |P| with β≈(1/ε)^{log k} (a near matching upper bound was recently shown in [Michael Elkin and Idan Shabat, 2023]). That is, the size overhead of pairwise spanners has similar bounds to the hopbound of hopsets, and to the additive stretch of spanners. We also extend the connection between pairwise spanners and hopsets to the large stretch regime, by showing nearly matching upper and lower bounds for P-pairwise α-spanners. In particular, we show that if |P|≈ n^{1+1/k}, then the size overhead is β≈k/α. A source-wise spanner is a special type of pairwise spanner, for which P = A×V for some A ⊆ V. A prioritized spanner is given also a ranking of the vertices V = (v₁,… ,v_n), and is required to provide improved stretch for pairs containing higher ranked vertices. By using a sequence of reductions: from pairwise spanners to source-wise spanners to prioritized spanners, we improve on the state-of-the-art results for source-wise and prioritized spanners. Since our spanners can be equipped with a path-reporting mechanism, we also substantially improve the known bounds for path-reporting prioritized distance oracles. Specifically, we provide a path-reporting distance oracle, with size O(n⋅(log log n)²), that has a constant stretch for any query that contains a vertex ranked among the first n^{1-δ} vertices (for any constant δ > 0). Such a result was known before only for non-path-reporting distance oracles.

Cite as

Ofer Neiman and Idan Shabat. On the Size Overhead of Pairwise Spanners. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 83:1-83:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{neiman_et_al:LIPIcs.ITCS.2024.83,
  author =	{Neiman, Ofer and Shabat, Idan},
  title =	{{On the Size Overhead of Pairwise Spanners}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{83:1--83:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.83},
  URN =		{urn:nbn:de:0030-drops-196110},
  doi =		{10.4230/LIPIcs.ITCS.2024.83},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, Spanners}
}

Document

DOI: 10.4230/LIPIcs.ESA.2022.81

A Unified Framework for Hopsets

Authors: Ofer Neiman and Idan Shabat

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract

Given an undirected graph G = (V,E), an (α,β)-hopset is a graph H = (V,E'), so that adding its edges to G guarantees every pair has an α-approximate shortest path that has at most β edges (hops), that is, d_G(u,v) ≤ d_{G∪H}^(β)(u,v) ≤ α⋅ d_G(u,v). Given the usefulness of hopsets for fundamental algorithmic tasks, several different algorithms and techniques were developed for their construction, for various regimes of the stretch parameter α. In this work we devise a single algorithm that can attain all state-of-the-art hopsets for general graphs, by choosing the appropriate input parameters. In fact, in some cases it also improves upon the previous best results. We also show a lower bound on our algorithm. In [Ben-Levy and Parter, 2020], given a parameter k, a (O(k^ε),O(k^{1-ε}))-hopset of size Õ(n^{1+1/k}) was shown for any n-vertex graph and parameter 0 < ε < 1, and they asked whether this result is best possible. We resolve this open problem, showing that any (α,β)-hopset of size O(n^{1+1/k}) must have α⋅β ≥ Ω(k).

Cite as

Ofer Neiman and Idan Shabat. A Unified Framework for Hopsets. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{neiman_et_al:LIPIcs.ESA.2022.81,
  author =	{Neiman, Ofer and Shabat, Idan},
  title =	{{A Unified Framework for Hopsets}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{81:1--81:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.81},
  URN =		{urn:nbn:de:0030-drops-170192},
  doi =		{10.4230/LIPIcs.ESA.2022.81},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, Hopsets}
}

Search Results

Documents authored by Shabat, Idan

Path-Reporting Distance Oracles with Linear Size

Abstract

Cite as

On the Size Overhead of Pairwise Spanners

Abstract

Cite as

A Unified Framework for Hopsets

Abstract

Cite as

Thanks for your feedback!

Could not send message