Bounded Independence Edge Subsampling in Graphs

Abstract

Random subsampling of edges is a common technique for designing efficient graph algorithms. In many applications, however, one seeks algorithms that use little or no randomness, which motivates the question of derandomization. A common first step in this direction is to reduce the amount of randomness required, for example by showing that an algorithm remains correct even when its randomness is drawn from a distribution with small support. Motivated by this perspective, we study bounded-independence edge subsampling in graphs. Most notably, we show:

O(log m)-wise independent edge subsampling with marginal probabilities 1/2 suffices for preserving connectivity in a graph with minimum cut >= k log(m) with probability 1 - 1/poly(m) (for a sufficiently large constant k).

O(log m)-wise 1/poly(m)-almost independent subsampling with marginal probabilities 1/2 suffices for ensuring cycle-freeness in a graph with shortest cycle length >= c log(m) with probability 1 - 1/poly(m) (for a sufficiently large constant c).

To demonstrate the utility of our results, we revisit the classic problem of using parallel algorithms for finding bases in graphic and cographic matroids, first studied in the work of Karp, Upfal, and Wigderson (FOCS 1985). In particular, we show that the optimal, randomized algorithms of Khanna, Putterman, and Song (arxiv 2025) can be explicitly derandomized while maintaining near-optimality.