Testing Connectedness and Edge Connectedness

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 $\epsilon$-testing connectedness of graphs with maximum degree at most $d$ requires $\Omega (\frac{1}{\epsilon }\log \frac{1}{\epsilon d})$ queries (when $\epsilon \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}{\epsilon }\log \frac{1}{\epsilon \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 $\Omega (k/\epsilon )$ queries.