Connectivity Labeling and Routing with Multiple Vertex Failures

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)

Abstract

We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An f-vertex/edge fault tolerant (f-V/EFT) connectivity labeling is a scheme that produces succinct labels for the vertices (and possibly to the edges) of an n-vertex graph G, such that given only the labels of two vertices s,t and of at most f faulty vertices/edges F, one can infer if s and t are connected in G-F. The primary complexity measure is the maximum label length (in bits). The f-EFT setting is relatively well understood: [Dory and Parter, PODC 2021] gave a randomized scheme with succinct labels of O(log3 n) bits, which was subsequently derandomized by [Izumi et al., PODC 2023] with Õ(f2)-bit labels. As both noted, handling vertex faults is more challenging. The known bounds for the f-VFT setting are far away: [Parter and Petruschka, DISC 2022] gave Õ(n1-1/2Θ(f))-bit labels, which is linear in n already for f =ω(loglogn). In this work we present an efficient f-VFT connectivity labeling scheme using poly(f, logn) bits. Specifically, we present a randomized scheme with O(f3 log5 n)-bit labels, and a derandomized version with O(f7 log13 n)-bit labels, compared to an ω(f)-bit lower bound on the required label length. Our schemes are based on a new low-degree graph decomposition that improves on [Duan and Pettie, SODA 2017], and facilitates its distributed representation into labels. This is accompanied with specialized linear graph sketches that extend the techniques of the Dory and Parter to the vertex fault setting, which are derandomized by adapting the approach of Izumi et al. and combining it with hit-miss hash families of [Karthik and Parter, SODA 2021]. Finally, we show that our labels naturally yield routing schemes avoiding a given set of at most f vertex failures with table and header sizes of only poly(f,logn) bits. This improves significantly over the linear size bounds implied by the EFT routing scheme of Dory and Parter.

Original languageEnglish
Title of host publicationSTOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing
EditorsBojan Mohar, Igor Shinkar, Ryan O�Donnell
Pages823-834
Number of pages12
ISBN (Electronic)9798400703836
DOIs
Publication statusPublished - 10 Jun 2024
Event56th Annual ACM Symposium on Theory of Computing, STOC 2024 - Vancouver, Canada
Duration: 24 Jun 202428 Jun 2024

Publication series

SeriesProceedings of the Annual ACM Symposium on Theory of Computing

Conference

Conference56th Annual ACM Symposium on Theory of Computing, STOC 2024
Country/TerritoryCanada
CityVancouver
Period24/6/2428/6/24

Funding

Supported by NSF Grant CCF-2221980, by the European Research Council (ERC) under the European Union’s Horizon 2020 Research and Innovation Programme, Grant Agreement No. 949083, and by the Israel Science Foundation (ISF), Grant 2084/18 Publisher Copyright: © 2024 Owner/Author.

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Connectivity Labeling and Routing with Multiple Vertex Failures'. Together they form a unique fingerprint.

Cite this