Erasure-Resilient Sublinear-Time Graph Algorithms

DOI10.1145/3488250zbMATH Open1495.68179arXiv2011.14291OpenAlexW4206799337MaRDI QIDQ5868882

Amit Levi, Sofya Raskhodnikova, Nithin M. Varma, Ramesh Krishnan S. Pallavoor

Publication date: 24 September 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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 $varepsilon$-far from connected and estimating the average degree. For testing connectedness, we discover a threshold phenomenon: when the fraction of erasures is less than $varepsilon$, this property can be tested efficiently (in time independent of the size of the graph); when the fraction of erasures is at least $varepsilon,$ 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 $varepsilon$. 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.

Full work available at URL: https://arxiv.org/abs/2011.14291

zbMATH Keywords

graph property testingapproximating graph parameterscomputing with incomplete information

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (1)

Testing connectedness of images

This page was built for publication: Erasure-Resilient Sublinear-Time Graph Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5868882)