arXiv preprint ·
Testing Connectedness and Edge Connectedness
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We revisit the classical problem of testing connectedness of graphs represented in the adjacency lists model and obtain optimal bounds. Specifically, we show that $\varepsilon$-testing connectedness of graphs with maximum degree at most $d$ requires $Ω(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon d})$ queries (when $\varepsilon \le \frac{1}{4d^5}$). Our result implies that the connectedness tester of Levi, Pallavoor, Raskhodnikova, and Varma ({\em ACM Trans.\ Comput.\ Theory, 2022}) is optimal. We also study the problem of testing $k$-edge-connectedness of both directed and undirected graphs of average degree $\overline{d}$ in the adjacency lists model and design a tester with query complexity $O(\frac{k}{\varepsilon} \log \frac{1}{\varepsilon \overline{d}})$, improving upon the bounds by Forster, Nanongkai, Saranurak, Yang, and Yingchareonthawornchai (SODA 2020). Furthermore, we complement our upper bound by showing that every one-sided error $k$-edge-connectedness tester must make $Ω(k/\varepsilon)$ queries.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
Competitive Online Clustering with Movement Cost
A 0.4584-approximation for DR-submodular maximization over down-closed convex sets
On the Metric Distortion of the Minimum Spanning Tree Problem
A General Framework for Matching with Delays
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.