2026-09-10T09:45:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27750 2026-09-09T12:19:36Z ddc:004 open_access

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries Adar, Tomer Hotam, Yahel Levi, Amit Edge count estimation Degree oracle Neighbor oracle Independent-set oracle We study the problem of estimating the number of edges in an unknown graph. We consider a hybrid model in which an algorithm may issue independent set, degree, and neighbor queries. We show that this model admits strictly more efficient edge estimation than either access type alone. Specifically, we give a randomized algorithm that outputs a (1±ε)-approximation of the number of edges using O(min(√m, √{n/√m})⋅(log n)/ε^{5/2}) queries, and prove a nearly matching lower bound. In contrast, prior work shows that in the local query model (Goldreich and Ron, Random Structures & Algorithms 2008) and in the independent set query model (Beame et al. ITCS 2018, Chen et al. SODA 2020), edge estimation requires Θ̃(n/√m) queries in the same parameter regimes. Our results therefore yield a quadratic improvement in the hybrid model, and no asymptotically better improvement is possible. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomer Adar and Yahel Hotam and Amit Levi 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.33 urn:nbn:de:0030-drops-277509 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.33 eng https://creativecommons.org/licenses/by/4.0/legalcode