Search Results

Documents authored by Petruschka, Asaf

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
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.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}
}
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 About DROPS Imprint Privacy Contact