Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
Tomer Adar, Amit Levi · 2026
Read Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries by Tomer Adar, Amit Levi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14306.txt.
Introduction
Adar and Levi study when counting edges in a graph can be turned into sampling edges almost uniformly. Two query types are in play: independent-set queries and local degree or neighbor queries. Prior work showed the tie in the local model alone. The authors extend it to a hybrid model that mixes both query types, and to independent-set queries alone. Matching lower bounds say sampling costs about the same as counting in each model. The results tighten the known link between the two tasks.
Catalog record
| CREATOR | Tomer Adar, Amit Levi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 130993 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.14306
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries Tomer Adar, Amit Levi Abstract 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 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 Chen, 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. 1 Introduction A fundamental question in the field of sublinear-time graph algorithms concerns the relationship between approximate counting and uniform sampling (see e.g, [ ER18 , ERR19 , AKK19 , FGP20 , EMR21 , DLM22 , AMM22 , ENT23 , ELRR25 ] ). Can the ability to estimate the size of a combinatorial structure, such as the number of edges of a graph G=(V,E) , be leveraged to sample an element of that structure nearly uniformly at essentially the same cost? The earliest investigation of this relationship focused on the case where the combinatorial structure is the set of edges E of an unknown graph G . In this setting, the relationship was first explored within the local query model. In this model, the algorithm is granted access to the graph’s adjacency list, allowing it to perform degree queries (returning the degree of a vertex v ) and neighbor queries (returning the i -th neighbor of a vertex v ). For a given \varepsilon\in(0,1) , the tasks are formally defined as follows: • Approximate counting: With high probability the algorithm outputs a value \tilde{\boldsymbol{m}} satisfying |E|(1-\varepsilon)\leq\tilde{\boldsymbol{m}}\leq(1+\varepsilon)|E| . • Almost uniform sampling: With high probability the algorithm outputs \boldsymbol{e} such that for every edge e\in E , {(1-\varepsilon)}/{|E|}\leq\operatorname{{\bf Pr}}[\boldsymbol{e}=e]\leq({1+\varepsilon})/{|E|} . While early edge sampling methods often required significantly higher complexity than counting [ KKR04 ] , a sequence of works [ ER18 , TT22 , ENT23 ] established that the query complexity of almost-uniform edge sampling is essentially equivalent to the query complexity of approximate edge counting (see [ GR08 ] ). Both tasks share query complexity of \widetilde{\Theta}(n/\sqrt{m}) , where n is the number of nodes and m is the number of edges in G and the tilde notation suppresses polynomial factors in \log n and 1/\varepsilon . Beame, Har-Peled, Ramamoorthy, Rashtchian, and Sinha [ BHPR+20 ] introduced a notably different global access by introducing the independent set oracle (IS). In this model, an algorithm may query any arbitrary subset S\subseteq V , and the oracle responds with a single bit indicating whether S induces an edge-free subgraph. Unlike local inspection, IS queries do not reveal the identity or specific location of edges. Instead, they provide coarse, global information about the presence or absence of edges within a queried set. This model can be viewed as a form of combinatorial group testing, where a single query probes a large portion of the graph simultaneously. As such, IS queries expose structural information that is fundamentally inaccessible through purely local inspection. The IS model and its variant received significant attention in the past years [ BBGM19 , BGMP19 , BBGM21 , DL21 , AMM22 , DLM22 , DLM24 ] (see more information in Section 1.2 ). In this model, the complexity of approximate edge count was settled by Chen, Levi and Waingarten [ CLW20 ] at \widetilde{\Theta}(\min\{\sqrt{m},n/\sqrt{m}\}) . Most recently, Adar, Hotam and Levi [ AHL26 ] considered a hybrid model which integrates global IS queries with local queries. They showed that the query complexity of approximate edge count is essentially \widetilde{\Theta}(\min\{\sqrt{m},\sqrt{n/\sqrt{m}}\}) . Nonetheless, the corresponding sampling problems in both the IS and the hybrid models remained open. 1.1 Our results In this paper, we bridge this gap by establishing that the sampling–counting equivalence extends to both the IS and Hybrid query models. In particular, we first present an efficient algorithm for edge sampling in the Hybrid model. Theorem 1.1 (note=Rephrase of Lemma , label=th:ubnd-hyb) . There exists an algorithm \nameref*{procname:sample-edge-hyb}(G,\varepsilon) where G is a graph over n vertices (known to the algorithm) and m edges (unknown to the algorithm) and \varepsilon>0 , that makes O(R\log n\log(n/\varepsilon)) degree, neighbor and independent-set queries, where R=\min\{\sqrt{m},\sqrt{n/\sqrt{m}}\} , whose random output \mathbf{X} satisfies: • \operatorname{{\bf Pr}}\left[\mathbf{X}\neq\textsc{reject}\right]\geq 2/3 . • For every edge e in G , \operatorname{{\bf Pr}}\left[\mathbf{X}=e\;\middle|\;\mathbf{X}\neq\textsc{reject}\right]\in(1\pm\varepsilon)/m . We complement this algorithmic result by showing that the query complexity of is optimal within the hybrid model, up to logarithmic factors. Theorem 1.2 (note=Rephrase of Lemma ) . Any algorithm whose behavior matches the guarantees of Theorem must make \Omega(\min\{\sqrt{m},\sqrt{n/\sqrt{m}}\}) queries in expectation. Next, we shift our focus to the more restricted Independent Set query model. Theorem 1.3 (note=Rephrase of Lemma , label=th:ubnd-IS) . There exists an algorithm \nameref*{procname:sample-edge-IS}(G,\varepsilon) where G is a graph over n vertices (known to the algorithm) and m edges (unknown to the algorithm) and \varepsilon>0 , that makes O(R\cdot\mathrm{poly}(\log(n/\varepsilon))) independent-set queries, where R=\min\{\sqrt{m},n/\sqrt{m}\} , whose random output \mathbf{X} satisfies: • \operatorname{{\bf Pr}}\left[\mathbf{X}\neq\textsc{reject}\right]\geq 2/3 . • For every edge e in G , \operatorname{{\bf Pr}}\left[\mathbf{X}=e\;\middle|\;\mathbf{X}\neq\textsc{reject}\right]\in(1\pm\varepsilon)/m . Finally, we establish a corresponding lower bound for the IS model, confirming that the dependence on m and n in Theorem is essentially tight. Theorem 1.4 (note=Rephrase of Lemma ) . Any algorithm whose behavior matches the guarantees of Theorem must make \Omega(\min\{\sqrt{m},n/\sqrt{m}\}) queries in expectation. 1.2 Related work Since the initial work in the local model, the problem of almost-uniform edge sampling has been extended to various settings. Eden, Ron, and Rosenbaum [ ERR19 ] showed that if a graph has bounded arboricity 1 1 1 Note that since \alpha\leq\sqrt{m} for every G with m edges, this result is at least as good as the result in [ ER18 , TT22 , ENT23 ] \alpha , the query complexity for almost-uniform sampling can be improved to \widetilde{O}(\alpha n/m) . Eden, Mossel and Rubinfeld [ EMR21 ] gave an algorithm which samples t edges using \widetilde{O}(\sqrt{t}\cdot n/\sqrt{m}) queries – a notable improvement compared to naively using t invocation of the edge sampler. This query complexity was later proved to be optimal by [ TT22 ] . Beyond the specific focus on edge estimation, several recent works have explored the broader problem of counting and sampling arbitrary subgraphs H within a variety of expanded query models. [ ERR22 ] extended the results of [ ERR19 ] for sampling k -cliques in the local model. In particular, their results show that for k -cliques sampling is harder than counting. In contrast, [ ELRR25 ] showed that for Hamiltonian subgraphs the complexity of counting and sampling coincides. Recent research has expanded the investigation of the sampling–counting relationship to arbitrary subgraphs H , utilizing various