Bounded Independence Edge Sampling for Combinatorial Graph Properties
This addresses the challenge of derandomizing graph algorithms for researchers in theoretical computer science, offering incremental improvements by generalizing prior bounded-independence results.
The paper tackles the problem of derandomizing randomized edge sampling in graph algorithms, showing that O(log(m))-wise independence suffices to preserve connectivity and cycle-freeness with high probability when sampling at half the edges, and applies this to explicitly derandomize near-optimal parallel algorithms for finding graphic matroid bases.
Random subsampling of edges is a commonly employed technique in graph algorithms, underlying a vast array of modern algorithmic breakthroughs. Unfortunately, using this technique often leads to randomized algorithms with no clear path to derandomization because the analyses rely on a union bound on exponentially many events. In this work, we revisit this goal of derandomizing randomized sampling in graphs. We give several results related to bounded-independence edge subsampling, and in the process of doing so, generalize several of the results of Alon and Nussboim (FOCS 2008), who studied bounded-independence analogues of random graphs (which can be viewed as edge subsamples of the complete graph). Most notably, we show: 1. $O(\log(m))$-wise independence suffices for preserving connectivity when sampling at rate $1/2$ in a graph with minimum cut $\geq κ\log(m)$ with probability $1 - \frac{1}{\mathrm{poly}(m)}$ (for a sufficiently large constant $κ$). 2. $O(\log(m))$-wise $\frac{1}{\mathrm{poly}(m)}$-almost independence suffices for ensuring cycle-freeness when sampling at rate $1/2$ in a graph with minimum cycle length $\geq κ\log(m)$ with probability $1 - \frac{1}{\mathrm{poly}(m)}$ (for a sufficiently large constant $κ$). To demonstrate the utility of our results, we revisit the classic problem of using parallel algorithms to find graphic matroid bases, first studied in the work of Karp, Upfal, and Wigderson (FOCS 1985). In this regime, we show that the optimal algorithms of Khanna, Putterman, and Song (arxiv 2025) can be explicitly derandomized while maintaining near-optimality.