DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.73

Towards Bypassing Lower Bounds for Graph Shortcuts

Authors: Shimon Kogan and Merav Parter

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

For a given (possibly directed) graph G, a hopset (a.k.a. shortcut set) is a (small) set of edges whose addition reduces the graph diameter while preserving desired properties from the given graph G, such as, reachability and shortest-path distances. The key objective is in optimizing the tradeoff between the achieved diameter and the size of the shortcut set (possibly also, the distance distortion). Despite the centrality of these objects and their thorough study over the years, there are still significant gaps between the known upper and lower bound results. A common property shared by almost all known shortcut lower bounds is that they hold for the seemingly simpler task of reducing the diameter of the given graph, D_G, by a constant additive term, in fact, even by just one! We denote such restricted structures by (D_G-1)-diameter hopsets. In this paper we show that this relaxation can be leveraged to narrow the current gaps, and in certain cases to also bypass the known lower bound results, when restricting to sparse graphs (with O(n) edges): - {Hopsets for Directed Weighted Sparse Graphs.} For every n-vertex directed and weighted sparse graph G with D_G ≥ n^{1/4}, one can compute an exact (D_G-1)-diameter hopset of linear size. Combining this with known lower bound results for dense graphs, we get a separation between dense and sparse graphs, hence shortcutting sparse graphs is provably easier. For reachability hopsets, we can provide (D_G-1)-diameter hopsets of linear size, for sparse DAGs, already for D_G ≥ n^{1/5}. This should be compared with the diameter bound of Õ(n^{1/3}) [Kogan and Parter, SODA 2022], and the lower bound of D_G = n^{1/6} by [Huang and Pettie, {SIAM} J. Discret. Math. 2018]. - {Additive Hopsets for Undirected and Unweighted Graphs.} We show a construction of +24 additive (D_G-1)-diameter hopsets with linear number of edges for D_G ≥ n^{1/12} for sparse graphs. This bypasses the current lower bound of D_G = n^{1/6} obtained for exact (D_G-1)-diameter hopset by [HP'18]. For general graphs, the bound becomes D_G ≥ n^{1/6} which matches the lower bound of exact (D_G-1) hopsets implied by [HP'18]. We also provide new additive D-diameter hopsets with linear size, for any given diameter D. Altogether, we show that the current lower bounds can be bypassed by restricting to sparse graphs (with O(n) edges). Moreover, the gaps are narrowed significantly for any graph by allowing for a constant additive stretch.

Cite as

Shimon Kogan and Merav Parter. Towards Bypassing Lower Bounds for Graph Shortcuts. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 73:1-73:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kogan_et_al:LIPIcs.ESA.2023.73,
  author =	{Kogan, Shimon and Parter, Merav},
  title =	{{Towards Bypassing Lower Bounds for Graph Shortcuts}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{73:1--73:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.73},
  URN =		{urn:nbn:de:0030-drops-187264},
  doi =		{10.4230/LIPIcs.ESA.2023.73},
  annote =	{Keywords: Directed Shortcuts, Hopsets, Emulators}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2023.85

New Additive Emulators

Authors: Shimon Kogan and Merav Parter

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract

For a given (possibly weighted) graph G = (V,E), an additive emulator H is a weighted graph in V × V that preserves the (all pairs) G-distances up to a small additive stretch. In their breakthrough result, [Abboud and Bodwin, STOC 2016] ruled out the possibility of obtaining o(n^{4/3})-size emulator with n^{o(1)} additive stretch. The focus of our paper is in the following question that has been explicitly stated in many of the prior work on this topic: What is the minimal additive stretch attainable with linear size emulators? The only known upper bound for this problem is given by an implicit construction of [Pettie, ICALP 2007] that provides a linear-size emulator with +Õ(n^{1/4}) stretch. No improvement on this problem has been shown since then. In this work we improve upon the long standing additive stretch of Õ(n^{1/4}), by presenting constructions of linear-size emulators with Õ(n^{0.222}) additive stretch. Our constructions improve the state-of-the-art size vs. stretch tradeoff in the entire regime. For example, for every ε > 1/7, we provide +n^{f(ε)} emulators of size Õ(n^{1+ε}), for f(ε) = 1/5-3ε/5. This should be compared with the current bound of f(ε) = 1/4-3ε/4 by [Pettie, ICALP 2007]. The new emulators are based on an extended and optimized toolkit for computing weighted additive emulators with sublinear distance error. Our key construction provides a weighted modification of the well-known Thorup and Zwick emulators [SODA 2006]. We believe that this TZ variant might be of independent interest, especially for providing improved stretch for distant pairs.

Cite as

Shimon Kogan and Merav Parter. New Additive Emulators. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 85:1-85:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kogan_et_al:LIPIcs.ICALP.2023.85,
  author =	{Kogan, Shimon and Parter, Merav},
  title =	{{New Additive Emulators}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{85:1--85:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.85},
  URN =		{urn:nbn:de:0030-drops-181377},
  doi =		{10.4230/LIPIcs.ICALP.2023.85},
  annote =	{Keywords: Spanners, Emulators, Distance Preservers}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2022.82

Beating Matrix Multiplication for n^{1/3}-Directed Shortcuts

Authors: Shimon Kogan and Merav Parter

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract

For an n-vertex digraph G = (V,E) and integer parameter D, a D-shortcut is a small set H of directed edges taken from the transitive closure of G, satisfying that the diameter of G ∪ H is at most D. A recent work [Kogan and Parter, SODA 2022] presented shortcutting algorithms with improved diameter vs. size tradeoffs. Most notably, obtaining linear size D-shortcuts for D = Õ(n^{1/3}), breaking the √n-diameter barrier. These algorithms run in O(n^{ω}) time, as they are based on the computation of the transitive closure of the graph. We present a new algorithmic approach for D-shortcuts, that matches the bounds of [Kogan and Parter, SODA 2022], while running in o(n^{ω}) time for every D ≥ n^{1/3}. Our approach is based on a reduction to the min-cost max-flow problem, which can be solved in Õ(m+n^{3/2}) time due to the recent breakthrough result of [Brand et al., STOC 2021]. We also demonstrate the applicability of our techniques to computing the minimal chain covers and dipath decompositions for directed acyclic graphs. For an n-vertex m-edge digraph G = (V,E), our key results are: - An Õ(n^{1/3}⋅ m+n^{3/2})-time algorithm for computing D-shortcuts of linear size for D = Õ(n^{1/3}), and an Õ(n^{1/4}⋅ m+n^{7/4})-time algorithm for computing D-shortcuts of Õ(n^{3/4}) edges for D = Õ(n^{1/2}). - For a DAG G, we provide Õ(m+n^{3/2})-time algorithms for computing its minimum chain covers, maximum antichain, and decomposition into dipaths and independent sets. This improves considerably over the state-of-the-art bounds by [Caceres et al., SODA 2022] and [Grandoni et al., SODA 2021]. Our results also provide a new connection between shortcutting sets and the seemingly less related problems of minimum chain covers and the maximum antichains in DAGs.

Cite as

Shimon Kogan and Merav Parter. Beating Matrix Multiplication for n^{1/3}-Directed Shortcuts. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 82:1-82:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kogan_et_al:LIPIcs.ICALP.2022.82,
  author =	{Kogan, Shimon and Parter, Merav},
  title =	{{Beating Matrix Multiplication for n^\{1/3\}-Directed Shortcuts}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{82:1--82:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.82},
  URN =		{urn:nbn:de:0030-drops-164230},
  doi =		{10.4230/LIPIcs.ICALP.2022.82},
  annote =	{Keywords: Directed Shortcuts, Transitive Closure, Width}
}

3 Search Results for "Kogan, Shimon"

Towards Bypassing Lower Bounds for Graph Shortcuts

Abstract

Cite as

New Additive Emulators

Abstract

Cite as

Beating Matrix Multiplication for n^{1/3}-Directed Shortcuts

Abstract

Cite as

Thanks for your feedback!

Could not send message