Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
This work addresses a foundational problem in sublinear graph algorithms for researchers, extending known equivalences to new query models.
The paper tackles the problem of uniform edge sampling in sublinear graph algorithms by establishing equivalence between sampling and counting in hybrid models combining independent-set and local queries, matching the complexity of prior edge-count estimation results.
A central theme in sublinear graph algorithms is the relationship between counting and sampling: can the ability to approximately count a combinatorial structure be leveraged to sample it nearly uniformly at essentially the same cost? We study (i) independent-set (IS) queries, which return whether a vertex set $S$ is edge-free, and (ii) two standard local queries: degree and neighbor queries. Eden and Rosenbaum (SOSA `18) proved that in the local-query model, uniform edge sampling is no harder than approximate edge counting. We extend this phenomenon to new settings. We establish sampling-counting equivalence for the hybrid model that combines IS and local queries, matching the complexity of edge-count estimation achieved by Adar, Hotam and Levi (2026), and an analogous equivalence for IS queries, matching the complexity of edge-count estimation achieved by Xi, Levi and Waingarten (SODA `20). For each query model, we show lower bounds for uniform edge sampling that essentially coincide with the known bounds for approximate edge counting.