Optimal query limits found for testing graph connectedness properties
Testing Connectedness and Edge Connectedness
Data Structures and Algorithms
Summary
The paper studies how hard it is to check if parts of a network are linked together. The authors find the best possible number of questions you need to ask about the network to tell if it's connected or if it remains connected even after some connections fail. They also improve testing methods for checking how many connection failures a network can handle, and show how many questions any tester must ask to be sure. This helps understand the limits of quickly checking network reliability.
What this means in practice
- •For network engineers: Optimize algorithms that quickly check if a communication network is reliably connected with minimal probing.
- •For distributed system developers: Improve tools that estimate network robustness to connection failures without extensive data collection.
A theory result. No direct application yet.
Authors
Diptaksho Palit, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma
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.