39 Search Results for "Parter, Merav"

Document
DOI: 10.4230/LIPIcs.DISC.2024.36
Connectivity Labeling in Faulty Colored Graphs

Authors: Asaf Petruschka, Shay Spair, and Elad Tzalik

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
Fault-tolerant connectivity labelings are schemes that, given an n-vertex graph G = (V,E) and a parameter f, produce succinct yet informative labels for the elements of the graph. Given only the labels of two vertices u,v and of the elements in a faulty-set F with |F| ≤ f, one can determine if u,v are connected in G-F, the surviving graph after removing F. For the edge or vertex faults models, i.e., F ⊆ E or F ⊆ V, a sequence of recent work established schemes with poly(f,log n)-bit labels for general graphs. This paper considers the color faults model, recently introduced in the context of spanners [Petruschka, Sapir and Tzalik, ITCS '24], which accounts for known correlations between failures. Here, the edges (or vertices) of the input G are arbitrarily colored, and the faulty elements in F are colors; a failing color causes all edges (vertices) of that color to crash. While treating color faults by naïvly applying solutions for many failing edges or vertices is inefficient, the known correlations could potentially be exploited to provide better solutions. Our main contribution is settling the label length complexity for connectivity under one color fault (f = 1). The existing implicit solution, by black-box application of the state-of-the-art scheme for edge faults of [Dory and Parter, PODC '21], might yield labels of Ω(n) bits. We provide a deterministic scheme with labels of Õ(√n) bits in the worst case, and a matching lower bound. Moreover, our scheme is universally optimal: even schemes tailored to handle only colorings of one specific graph topology (i.e., may store the topology "for free") cannot produce asymptotically smaller labels. We characterize the optimal length by a new graph parameter bp(G) called the ball packing number. We further extend our labeling approach to yield a routing scheme avoiding a single forbidden color, with routing tables of size Õ(bp(G)) bits. We also consider the centralized setting, and show an Õ(n)-space oracle, answering connectivity queries under one color fault in Õ(1) time. Curiously, by our results, no oracle with such space can be evenly distributed as labels. Turning to f ≥ 2 color faults, we give a randomized labeling scheme with Õ(n^{1-1/2^f})-bit labels, along with a lower bound of Ω(n^{1-1/(f+1)}) bits. For f = 2, we make partial improvement by providing labels of Õ(diam(G)√n) bits, and show that this scheme is (nearly) optimal when diam(G) = Õ(1). Additionally, we present a general reduction from the above all-pairs formulation of fault-tolerant connectivity labeling (in any fault model) to the single-source variant, which could also be applicable for centralized oracles, streaming, or dynamic algorithms.
Cite as

Asaf Petruschka, Shay Spair, and Elad Tzalik. Connectivity Labeling in Faulty Colored Graphs. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{petruschka_et_al:LIPIcs.DISC.2024.36,
  author =	{Petruschka, Asaf and Spair, Shay and Tzalik, Elad},
  title =	{{Connectivity Labeling in Faulty Colored Graphs}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{36:1--36:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.36},
  URN =		{urn:nbn:de:0030-drops-212622},
  doi =		{10.4230/LIPIcs.DISC.2024.36},
  annote =	{Keywords: Labeling schemes, Fault-tolerance}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.40
Brief Announcement: Distributed Maximum Flow in Planar Graphs

Authors: Yaseen Abd-Elhaleem, Michal Dory, Merav Parter, and Oren Weimann

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
The dual of a planar graph G is a planar graph G^* that has a vertex for each face of G and an edge for each pair of adjacent faces of G. The profound relationship between a planar graph and its dual has been the algorithmic basis for solving numerous (centralized) classical problems on planar graphs involving distances, flows, and cuts. In the distributed setting however, the only use of planar duality is for finding a recursive decomposition of G [DISC 2017, STOC 2019]. In this paper, we extend the distributed algorithmic toolkit (such as recursive decompositions and minor-aggregations) to work on the dual graph G^*. These tools can then facilitate various algorithms on G by solving a suitable dual problem on G^*. Given a directed planar graph G with hop-diameter D, our key result is an Õ(D²)-round algorithm for Single Source Shortest Paths on G^*, which then implies an Õ(D²)-round algorithm for Maximum st-Flow on G. Prior to our work, no Õ(Poly(D))-round algorithm was known for Maximum st-Flow. We further obtain a D⋅ n^o(1)-rounds (1+ε)-approximation algorithm for Maximum st-Flow on G when G is undirected and s and t lie on the same face. Finally, we give a near optimal Õ(D)-round algorithm for computing the weighted girth of G. The main challenges in our work are that G^* is not the communication graph (e.g., a vertex of G is mapped to multiple vertices of G^*), and that the diameter of G^* can be much larger than D (i.e., possibly by a linear factor). We overcome these challenges by carefully defining and maintaining subgraphs of the dual graph G^* while applying the recursive decomposition on the primal graph G. The main technical difficulty, is that along the recursive decomposition, a face of G gets shattered into (disconnected) components yet we still need to treat it as a dual node.
Cite as

Yaseen Abd-Elhaleem, Michal Dory, Merav Parter, and Oren Weimann. Brief Announcement: Distributed Maximum Flow in Planar Graphs. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 40:1-40:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abdelhaleem_et_al:LIPIcs.DISC.2024.40,
  author =	{Abd-Elhaleem, Yaseen and Dory, Michal and Parter, Merav and Weimann, Oren},
  title =	{{Brief Announcement: Distributed Maximum Flow in Planar Graphs}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{40:1--40:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.40},
  URN =		{urn:nbn:de:0030-drops-212687},
  doi =		{10.4230/LIPIcs.DISC.2024.40},
  annote =	{Keywords: Maximum flow, shortest paths, planar graphs, distributed computing}
}
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
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2024.4
Graphs Shortcuts: New Bounds and Algorithms (Invited Talk)

Authors: Merav Parter

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
For an n-vertex digraph G = (V,E), a shortcut set is a (small) subset of edges H taken from the transitive closure of G that, when added to G guarantees that the diameter of G ∪ H is small. Shortcut sets, introduced by Thorup in 1993, have a wide range of applications in algorithm design, especially in the context of parallel, distributed and dynamic computation on directed graphs. A folklore result in this context shows that every n-vertex digraph admits a shortcut set of linear size (i.e., of O(n) edges) that reduces the diameter to Õ(√n). Despite extensive research over the years, the question of whether one can reduce the diameter to o(√n) with Õ(n) shortcut edges has been left open. In this talk, I will present the first improved diameter-sparsity tradeoff for this problem, breaking the √n diameter barrier. Specifically, we show an O(n^ω)-time randomized algorithm for computing a linear shortcut set that reduces the diameter of the digraph to Õ(n^{1/3}). I also present time efficient algorithms for computing these shortcuts and explain the limitations of the current approaches. Finally, I will draw some connections between shortcuts and several forms of graph sparsification (e.g., reachability preservers, spanners). Based on a joint work with Shimon Kogan (SODA 2022, ICALP 2022, FOCS 2022, SODA 2023).
Cite as

Merav Parter. Graphs Shortcuts: New Bounds and Algorithms (Invited Talk). In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{parter:LIPIcs.ICALP.2024.4,
  author =	{Parter, Merav},
  title =	{{Graphs Shortcuts: New Bounds and Algorithms}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.4},
  URN =		{urn:nbn:de:0030-drops-201476},
  doi =		{10.4230/LIPIcs.ICALP.2024.4},
  annote =	{Keywords: Shortcuts, Spanners, Distance Preservers}
}
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.19
Spanning Adjacency Oracles in Sublinear Time

Authors: Greg Bodwin and Henry Fleischmann

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

Abstract
Suppose we are given an n-node, m-edge input graph G, and the goal is to compute a spanning subgraph H on O(n) edges. This can be achieved in linear O(m + n) time via breadth-first search. But can we hope for sublinear runtime in some range of parameters - for example, perhaps O(n^{1.9}) worst-case runtime, even when the input graph has n² edges? If the goal is to return H as an adjacency list, there are simple lower bounds showing that Ω(m + n) runtime is necessary. If the goal is to return H as an adjacency matrix, then we need Ω(n²) time just to write down the entries of the output matrix. However, we show that neither of these lower bounds still apply if instead the goal is to return H as an implicit adjacency matrix, which we call an adjacency oracle. An adjacency oracle is a data structure that gives a user the illusion that an adjacency matrix has been computed: it accepts edge queries (u, v), and it returns in near-constant time a bit indicating whether or not (u, v) ∈ E(H). Our main result is that, for any 0 < ε < 1, one can construct an adjacency oracle for a spanning subgraph on at most (1+ε)n edges, in Õ(n ε^{-1}) time (hence sublinear time on input graphs with m ≫ n edges), and that this construction time is near-optimal. Additional results include constructions of adjacency oracles for k-connectivity certificates and spanners, which are similarly sublinear on dense-enough input graphs. Our adjacency oracles are closely related to Local Computation Algorithms (LCAs) for graph sparsifiers; they can be viewed as LCAs with some computation moved to a preprocessing step, in order to speed up queries. Our oracles imply the first LCAs for computing sparse spanning subgraphs of general input graphs in Õ(n) query time, which works by constructing our adjacency oracle, querying it once, and then throwing the rest of the oracle away. This addresses an open problem of Rubinfeld [CSR '17].
Cite as

Greg Bodwin and Henry Fleischmann. Spanning Adjacency Oracles in Sublinear Time. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bodwin_et_al:LIPIcs.ITCS.2024.19,
  author =	{Bodwin, Greg and Fleischmann, Henry},
  title =	{{Spanning Adjacency Oracles in Sublinear Time}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{19:1--19:21},
  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.19},
  URN =		{urn:nbn:de:0030-drops-195475},
  doi =		{10.4230/LIPIcs.ITCS.2024.19},
  annote =	{Keywords: Graph algorithms, Sublinear algorithms, Data structures, Graph theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.88
Color Fault-Tolerant Spanners

Authors: Asaf Petruschka, Shay Sapir, and Elad Tzalik

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

Abstract
We initiate the study of spanners in arbitrarily vertex- or edge-colored graphs (with no "legality" restrictions), that are resilient to failures of entire color classes. When a color fails, all vertices/edges of that color crash. An f-color fault-tolerant (f-CFT) t-spanner of an n-vertex colored graph G is a subgraph H that preserves distances up to factor t, even in the presence of at most f color faults. This notion generalizes the well-studied f-vertex/edge fault-tolerant (f-V/EFT) spanners. The size (number of edges) of an f-V/EFT spanner crucially depends on the number f of vertex/edge faults to be tolerated. In the colored variants, even a single color fault can correspond to an unbounded number of vertex/edge faults. The key conceptual contribution of this work is in showing that the size required by an f-CFT spanner is in fact comparable to its uncolored counterpart, with no dependency on the size of color classes. We provide optimal bounds on the size required by f-CFT (2k-1)-spanners, as follows: - When vertices have colors, we show an upper bound of O(f^{1-1/k} n^{1+1/k}) edges. This precisely matches the (tight) bounds for (2k-1)-spanners resilient to f individual vertex faults [Bodwin et al., SODA 2018; Bodwin and Patel, PODC 2019]. - For colored edges, we show that O(f n^{1+1/k}) edges are always sufficient. Further, we prove this is tight, i.e., we provide an Ω(f n^{1+1/k}) (worst-case) lower bound. The state-of-the-art bounds known for the corresponding uncolored setting of edge faults are (roughly) Θ(f^{1/2} n^{1+1/k}) [Bodwin et al., SODA 2018; Bodwin, Dinitz and Robelle, SODA 2022]. - We also consider a mixed model where both vertices and edges are colored. In this case, we show tight Θ(f^{2-1/k} n^{1+1/k}) bounds. Thus, CFT spanners exhibit an interesting phenomenon: while (individual) edge faults are "easier" than vertex faults, edge-color faults are "harder" than vertex-color faults. Our upper bounds are based on a generalization of the blocking set technique of [Bodwin and Patel, PODC 2019] for analyzing the (exponential-time) greedy algorithm for FT spanners. We complement them by providing efficient constructions of CFT spanners with similar size guarantees, based on the algorithm of [Dinitz and Robelle, PODC 2020].
Cite as

Asaf Petruschka, Shay Sapir, and Elad Tzalik. Color Fault-Tolerant Spanners. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 88:1-88:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{petruschka_et_al:LIPIcs.ITCS.2024.88,
  author =	{Petruschka, Asaf and Sapir, Shay and Tzalik, Elad},
  title =	{{Color Fault-Tolerant Spanners}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{88:1--88:17},
  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.88},
  URN =		{urn:nbn:de:0030-drops-196160},
  doi =		{10.4230/LIPIcs.ITCS.2024.88},
  annote =	{Keywords: Fault tolerance, Graph spanners}
}
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
DOI: 10.4230/LIPIcs.ITCS.2023.71
Secure Distributed Network Optimization Against Eavesdroppers

Authors: Yael Hitron, Merav Parter, and Eylon Yogev

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We present a new algorithmic framework for distributed network optimization in the presence of eavesdropper adversaries, also known as passive wiretappers. In this setting, the adversary is listening to the traffic exchanged over a fixed set of edges in the graph, trying to extract information on the private input and output of the vertices. A distributed algorithm is denoted as f-secure, if it guarantees that the adversary learns nothing on the input and output for the vertices, provided that it controls at most f graph edges. Recent work has presented general simulation results for f-secure algorithms, with a round overhead of D^Θ(f), where D is the diameter of the graph. In this paper, we present a completely different white-box, and yet quite general, approach for obtaining f-secure algorithms for fundamental network optimization tasks. Specifically, for n-vertex D-diameter graphs with (unweighted) edge-connectivity Ω(f), there are f-secure congest algorithms for computing MST, partwise aggregation, and (1+ε) (weighted) minimum cut approximation, within Õ(D+f √n) congest rounds, hence nearly tight for f = Õ(1). Our algorithms are based on designing a secure algorithmic-toolkit that leverages the special structure of congest algorithms for global optimization graph problems. One of these tools is a general secure compiler that simulates light-weight distributed algorithms in a congestion-sensitive manner. We believe that these tools set the ground for designing additional secure solutions in the congest model and beyond.
Cite as

Yael Hitron, Merav Parter, and Eylon Yogev. Secure Distributed Network Optimization Against Eavesdroppers. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 71:1-71:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hitron_et_al:LIPIcs.ITCS.2023.71,
  author =	{Hitron, Yael and Parter, Merav and Yogev, Eylon},
  title =	{{Secure Distributed Network Optimization Against Eavesdroppers}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{71:1--71:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.71},
  URN =		{urn:nbn:de:0030-drops-175746},
  doi =		{10.4230/LIPIcs.ITCS.2023.71},
  annote =	{Keywords: congest, secure computation, network optimization}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.27
Broadcast CONGEST Algorithms Against Eavesdroppers

Authors: Yael Hitron, Merav Parter, and Eylon Yogev

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
An eavesdropper is a passive adversary that aims at extracting private information on the input and output values of the network’s participants, by listening to the traffic exchanged over a subset of edges in the graph. We consider secure congest algorithms for the basic broadcast task, in the presence of eavesdropper (edge) adversaries. For D-diameter n-vertex graphs with edge connectivity Θ(f), we present f-secure broadcast algorithms that run in Õ(D+√{f n}) rounds. These algorithms transmit some broadcast message m^* to all the vertices in the graph, in a way that is information-theoretically secure against an eavesdropper controlling any subset of at most f edges in the graph. While our algorithms are heavily based on network coding (secret sharing), we also show that this is essential. For the basic problem of secure unicast we demonstrate a network coding gap of Ω(n) rounds. In the presence of vertex adversaries, known as semi-honest, we introduce the Forbidden-Set Broadcast problem: In this problem, the vertices of the graph are partitioned into two sets, trusted and untrusted, denoted as R, F ⊆ V, respectively, such that G[R] is connected. It is then desired to exchange a secret message m^* between all the trusted vertices while leaking no information to the untrusted set F. Our algorithm works in Õ(D+√|R|) rounds and its security guarantees hold even when all the untrusted vertices F are controlled by a (centralized) adversary.
Cite as

Yael Hitron, Merav Parter, and Eylon Yogev. Broadcast CONGEST Algorithms Against Eavesdroppers. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hitron_et_al:LIPIcs.DISC.2022.27,
  author =	{Hitron, Yael and Parter, Merav and Yogev, Eylon},
  title =	{{Broadcast CONGEST Algorithms Against Eavesdroppers}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{27:1--27:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.27},
  URN =		{urn:nbn:de:0030-drops-172186},
  doi =		{10.4230/LIPIcs.DISC.2022.27},
  annote =	{Keywords: congest, edge-connectivity, secret sharing}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.31
Near-Optimal Distributed Computation of Small Vertex Cuts

Authors: Merav Parter and Asaf Petruschka

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
We present near-optimal algorithms for detecting small vertex cuts in the {CONGEST} model of distributed computing. Despite extensive research in this area, our understanding of the vertex connectivity of a graph is still incomplete, especially in the distributed setting. To this date, all distributed algorithms for detecting cut vertices suffer from an inherent dependency in the maximum degree of the graph, Δ. Hence, in particular, there is no truly sub-linear time algorithm for this problem, not even for detecting a single cut vertex. We take a new algorithmic approach for vertex connectivity which allows us to bypass the existing Δ barrier. - As a warm-up to our approach, we show a simple Õ(D)-round randomized algorithm for computing all cut vertices in a D-diameter n-vertex graph. This improves upon the O(D+Δ/log n)-round algorithm of [Pritchard and Thurimella, ICALP 2008]. - Our key technical contribution is an Õ(D)-round randomized algorithm for computing all cut pairs in the graph, improving upon the state-of-the-art O(Δ ⋅ D)⁴-round algorithm by [Parter, DISC '19]. Note that even for the considerably simpler setting of edge cuts, currently Õ(D)-round algorithms are currently known only for detecting pairs of cut edges. Our approach is based on employing the well-known linear graph sketching technique [Ahn, Guha and McGregor, SODA 2012] along with the heavy-light tree decomposition of [Sleator and Tarjan, STOC 1981] . Combining this with a careful characterization of the survivable subgraphs, allows us to determine the connectivity of G ⧵ {x,y} for every pair x,y ∈ V, using Õ(D)-rounds. We believe that the tools provided in this paper are useful for omitting the Δ-dependency even for larger cut values.
Cite as

Merav Parter and Asaf Petruschka. Near-Optimal Distributed Computation of Small Vertex Cuts. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{parter_et_al:LIPIcs.DISC.2022.31,
  author =	{Parter, Merav and Petruschka, Asaf},
  title =	{{Near-Optimal Distributed Computation of Small Vertex Cuts}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{31:1--31:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.31},
  URN =		{urn:nbn:de:0030-drops-172223},
  doi =		{10.4230/LIPIcs.DISC.2022.31},
  annote =	{Keywords: Vertex-connectivity, Congest, Graph Sketches}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.32
Õptimal Dual Vertex Failure Connectivity Labels

Authors: Merav Parter and Asaf Petruschka

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
In this paper we present succinct labeling schemes for supporting connectivity queries under vertex faults. For a given n-vertex graph G, an f-VFT (resp., EFT) connectivity labeling scheme is a distributed data structure that assigns each of the graph edges and vertices a short label, such that given the labels of a vertex pair u and v, and the labels of at most f failing vertices (resp., edges) F, one can determine if u and v are connected in G ⧵ F. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS '07], FT labeling schemes have been devised only for a limited collection of graph families. A recent work [Dory and Parter, PODC 2021] provided EFT labeling schemes for general graphs under edge failures, leaving the vertex failure case fairly open. We provide the first sublinear f-VFT labeling schemes for f ≥ 2 for any n-vertex graph. Our key result is 2-VFT connectivity labels with O(log³ n) bits. Our constructions are based on analyzing the structure of dual failure replacement paths on top of the well-known heavy-light tree decomposition technique of [Sleator and Tarjan, STOC 1981]. We also provide f-VFT labels with sub-linear length (in |V|) for any f = o(log log n), that are based on a reduction to the existing EFT labels.
Cite as

Merav Parter and Asaf Petruschka. Õptimal Dual Vertex Failure Connectivity Labels. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{parter_et_al:LIPIcs.DISC.2022.32,
  author =	{Parter, Merav and Petruschka, Asaf},
  title =	{{\~{O}ptimal Dual Vertex Failure Connectivity Labels}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.32},
  URN =		{urn:nbn:de:0030-drops-172239},
  doi =		{10.4230/LIPIcs.DISC.2022.32},
  annote =	{Keywords: Fault-Tolerance, Heavy-Light Decomposition, Labeling Schemes}
}
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}
}
  • Refine by Author
  • 34 Parter, Merav
  • 8 Hitron, Yael
  • 5 Kogan, Shimon
  • 4 Musco, Cameron
  • 4 Petruschka, Asaf
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 4 Distributed Graph Algorithms
  • 3 CONGEST
  • 3 Distance Preservers
  • 3 Spanners
  • 2 Coloring
  • Show More...

  • Refine by Type
  • 39 document

  • Refine by Publication Year
  • 8 2024
  • 7 2020
  • 6 2017
  • 5 2022
  • 4 2018
  • Show More...

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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact