Erasure-resilient sublinear-time graph algorithms
Files
First author draft
Date
2020
DOI
Authors
Levi, Amit
Pallavoor, Ramesh Krishnan S.
Raskhodnikova, Sofya
Varma, Nithin
Version
First author draft
OA Version
Citation
A. Levi, R.K.S. Pallavoor, S. Raskhodnikova, N. Varma. 2020. "Erasure-Resilient Sublinear-Time Graph Algorithms.." CoRR, Volume abs/2011.14291, https://arxiv.org/abs/2011.14291
Abstract
We investigate sublinear-time algorithms that take partially erased graphs represented by
adjacency lists as input. Our algorithms make degree and neighbor queries to the input graph
and work with a specified fraction of adversarial erasures in adjacency entries. We focus on two
computational tasks: testing if a graph is connected or ε-far from connected and estimating
the average degree. For testing connectedness, we discover a threshold phenomenon: when the
fraction of erasures is less than ε, this property can be tested efficiently (in time independent of
the size of the graph); when the fraction of erasures is at least ε, then a number of queries linear
in the size of the graph representation is required. Our erasure-resilient algorithm (for the special
case with no erasures) is an improvement over the previously known algorithm for connectedness
in the standard property testing model and has optimal dependence on the proximity parameter
ε. For estimating the average degree, our results provide an “interpolation” between the query
complexity for this computational task in the model with no erasures in two different settings:
with only degree queries, investigated by Feige (SIAM J. Comput. ‘06), and with degree queries
and neighbor queries, investigated by Goldreich and Ron (Random Struct. Algorithms ‘08) and
Eden et al. (ICALP ‘17). We conclude with a discussion of our model and open questions raised
by our work.
Description
License
This work is distributed under a Creative Commons Attribution 4.0 International (CC BY 4.0) license.