Search Results

Documents authored by Kogan, Shimon

Document
DOI: 10.4230/LIPIcs.ESA.2024.79
Giving Some Slack: Shortcuts and Transitive Closure Compressions

Authors: Shimon Kogan and Merav Parter

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We consider the fundamental problems of reachability shortcuts and compression schemes of the transitive closure (TC) of n-vertex directed acyclic graphs (DAGs) G when we are allowed to neglect the distance (or reachability) constraints for an ε fraction of the pairs in the transitive closure of G, denoted by TC(G). Shortcuts with Slack. For a directed graph G = (V,E), a d-reachability shortcut is a set of edges H ⊆ TC(G), whose addition decreases the directed diameter of G to be at most d. We introduce the notion of shortcuts with slack which provide the desired distance bound d for all but a small fraction ε of the vertex pairs in TC(G). For ε ∈ (0,1), a (d,ε)-shortcut H ⊆ TC(G) is a subset of edges with the property that dist_{G ∪ H}(u,v) ≤ d for at least (1-ε) fraction of the (u,v) pairs in TC(G). Our constructions hold for any DAG G and their size bounds are parameterized by the width of the graph G defined by the smallest number of directed paths in G that cover all vertices in G. - For every ε ∈ (0,1] and integer d ≥ 5, every n-vertex DAG G of width {ω} admits a (d,ε)-shortcut of size Õ({ω}²/(ε d)+n). A more delicate construction yields a (3,ε)-shortcut of size Õ({ω}²/(ε d)+n/ε), hence of linear size for {ω} ≤ √n. We show that without a slack (i.e., for ε = 0), graphs with {ω} ≤ √n cannot be shortcut to diameter below n^{1/6} using a linear number of shortcut edges. - There exists an n-vertex DAG G for which any (3,ε = 1/2^{√{log ω}})-shortcut set has Ω({ω}²/2^{√{log ω}}+n) edges. Hence, for d = Õ(1), our constructions are almost optimal. Approximate TC Representations. A key application of our shortcut’s constructions is a (1-ε)-approximate all-successors data structure which given a vertex v, reports a list containing (1-ε) fraction of the successors of v in the graph. We present a Õ({ω}²/ε+n)-space data structure with a near linear (in the output size) query time. Using connections to Error Correcting Codes, we also present a near-matching space lower bound of Ω({ω}²+n) bits (regardless of the query time) for constant ε. This improves upon the state-of-the-art space bounds of O({ω} ⋅ n) for ε = 0 by the prior work of Jagadish [ACM Trans. Database Syst., 1990].
Cite as

Shimon Kogan and Merav Parter. Giving Some Slack: Shortcuts and Transitive Closure Compressions. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 79:1-79:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kogan_et_al:LIPIcs.ESA.2024.79,
  author =	{Kogan, Shimon and Parter, Merav},
  title =	{{Giving Some Slack: Shortcuts and Transitive Closure Compressions}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{79:1--79:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.79},
  URN =		{urn:nbn:de:0030-drops-211509},
  doi =		{10.4230/LIPIcs.ESA.2024.79},
  annote =	{Keywords: Reachability Shortcuts, Width, DAG}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.80
The Algorithmic Power of the Greene-Kleitman Theorem

Authors: Shimon Kogan and Merav Parter

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
For a given n-vertex DAG G = (V,E) with transitive-closure TC(G), a chain is a directed path in TC(G) and an antichain is an independent set in TC(G). The maximum k-antichain problem asks for computing the maximum k-colorable subgraph of the transitive closure. The related maximum h-chains problem asks for computing h disjoint chains (i.e., cliques in TC(G)) of largest total lengths. The celebrated Greene-Kleitman (GK) theorem [J. of Comb. Theory, 1976] demonstrates the (combinatorial) connections between these two problems. In this work we translate the combinatorial properties implied by the GK theorem into time-efficient covering algorithms. In contrast to prior results, our algorithms are applied directly on G, and do not require the precomputation of its transitive closure. Let α_k(G) be the maximum number of vertices that can be covered by k antichains. We show: - For every n-vertex m-edge DAG G = (V,E), one can compute at most (2k-1) disjoint antichains that cover α_k(G) vertices in time m^{1+o(1)} (hence, independent in k). This extends the recent m^{1+o(1)}-time Maximum-Antichain algorithm (where k = 1) by [Cáceres et al., SODA 2022] to any value of k. - For every n-vertex m-edge Partially-Ordered-Set (poset) P = (V,E), one can compute (1+ε)k disjoint antichains that cover α_k(P) vertices in time O(√m⋅ α_k(P)⋅ n^{o(1)}/ε), hence at most n^{2+o(1)}/ε. This improves over the exact solution of O(n³) time of [Gavril, Networks 1987] at the cost of producing (1+ε)k antichains instead of exactly k. The heart of our approach is a linear-time greedy-like algorithm that translates suitable chain collections 𝒞 into an parallel set of antichains 𝒜, in which |C_j ∩ A_i| = 1 for every C_j ∈ 𝒞 and A_i ∈ 𝒜. The correctness of this approach is underlined by the GK theorem.
Cite as

Shimon Kogan and Merav Parter. The Algorithmic Power of the Greene-Kleitman Theorem. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kogan_et_al:LIPIcs.ESA.2024.80,
  author =	{Kogan, Shimon and Parter, Merav},
  title =	{{The Algorithmic Power of the Greene-Kleitman Theorem}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.80},
  URN =		{urn:nbn:de:0030-drops-211512},
  doi =		{10.4230/LIPIcs.ESA.2024.80},
  annote =	{Keywords: Chains, Antichains, DAG}
}
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 Õ(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.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 +Õ(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 Õ(n^{1/4}), by presenting constructions of linear-size emulators with Õ(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 Õ(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.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 = Õ(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 Õ(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 Õ(n^{1/3}⋅ m+n^{3/2})-time algorithm for computing D-shortcuts of linear size for D = Õ(n^{1/3}), and an Õ(n^{1/4}⋅ m+n^{7/4})-time algorithm for computing D-shortcuts of Õ(n^{3/4}) edges for D = Õ(n^{1/2}). - For a DAG G, we provide Õ(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.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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact