Document Open Access Logo

Edge Estimation with Independent Set Oracles

Authors Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.38.pdf
  • Filesize: 0.68 MB
  • 21 pages

Document Identifiers

Author Details

Paul Beame
Sariel Har-Peled
Sivaramakrishnan Natarajan Ramamoorthy
Cyrus Rashtchian
Makrand Sinha

Cite As Get BibTex

Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. Edge Estimation with Independent Set Oracles. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.38

Abstract

We study the problem of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have applications to the complexity of decision versus counting problems. We give two algorithms to estimate the number of edges in an n-vertex graph: one that uses only polylog(n) bipartite independent set queries, and another one that uses n^{2/3} polylog(n) independent set queries.

Subject Classification

Keywords
  • Approximate Counting
  • Independent Set Queries
  • Sparsification
  • Importance Sampling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. B. Aronov and S. Har-Peled. On Approximating the Depth and Related Problems. SIAM J. Comput., 38(3):899-921, 2008. Google Scholar
  2. Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. Edge Estimation with Independent Set Oracles. CoRR, abs/1711.07567, 2017. URL: http://arxiv.org/abs/1711.07567.
  3. Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, and Dana Ron. Comparing the strength of query types in property testing: The case of k-colorability. Computational Complexity, 22(1):89-135, 2013. Google Scholar
  4. Sergio Cabello and Miha Jejčič. Shortest paths in intersection graphs of unit disks. Computational Geometry, 48(4):360-367, 2015. Google Scholar
  5. Chao L Chen and William H Swallow. Using Group Testing to Estimate a Proportion, and to Test the Binomial Model. Biometrics, pages 1035-1046, 1990. Google Scholar
  6. Holger Dell and John Lapinskas. Fine-grained reductions from approximate counting to decision. CoRR, abs/1707.04609, 2017. Google Scholar
  7. Robert Dorfman. The Detection of Defective Members of Large Populations. The Annals of Mathematical Statistics, 14(4):436-440, 1943. Google Scholar
  8. Devdatt P Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. Google Scholar
  9. T. Eden, D. Ron, and C. Seshadhri. On Approximating the Number of k-cliques in Sublinear Time. ArXiv e-prints, 2017. URL: http://arxiv.org/abs/1707.04858.
  10. Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. Approximately counting triangles in sublinear time. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 614-633. IEEE Computer Society, 2015. Google Scholar
  11. Talya Eden and Will Rosenbaum. On Sampling Edges Almost Uniformly. arXiv preprint arXiv:1706.09748, 2017. Google Scholar
  12. Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Estimating the number of defectives with group testing. In ISIT, pages 1376-1380. IEEE, 2016. Google Scholar
  13. Uriel Feige. On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM Journal on Computing, 35(4):964-984, 2006. Google Scholar
  14. Aleksei V Fishkin. Disk graphs: A short survey. In International Workshop on Approximation and Online Algorithms, pages 260-264. Springer, 2003. Google Scholar
  15. Oded Goldreich and Dana Ron. Approximating average parameters of graphs. Random Structures &Algorithms, 32(4):473-493, 2008. Google Scholar
  16. Mira Gonen, Dana Ron, and Yuval Shavitt. Counting stars and other small subgraphs in sublinear-time. SIAM J. Discrete Math, 25(3):1365-1411, 2011. Google Scholar
  17. Robert J Klein, Caroline Zeiss, Emily Y Chew, Jen-Yue Tsai, Richard S Sackler, Chad Haynes, Alice K Henning, John Paul SanGiovanni, Shrikant M Mane, Susan T Mayne, et al. Complement factor h polymorphism in age-related macular degeneration. Science, 308(5720):385-389, 2005. Google Scholar
  18. Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. CoRR, abs/1110.1079, 2011. Google Scholar
  19. Dana Ron and Gilad Tsur. The power of an example: Hidden set size approximation using group queries and conditional sampling. CoRR, abs/1404.5568, 2014. Google Scholar
  20. C. Seshadhri. A simpler sublinear algorithm for approximating the triangle count. ArXiv e-prints, 2015. URL: http://arxiv.org/abs/1505.01927.
  21. Larry Stockmeyer. The complexity of approximate counting (preliminary version). In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 118-126, Boston, Massachusetts, 25-27 1983. Google Scholar
  22. Larry Stockmeyer. On approximation algorithms for #P. SICOMP: SIAM Journal on Computing, 14, 1985. Google Scholar
  23. William H Swallow. Group Testing for Estimating Infection Rates and Probabilities of Disease Transmission. Phytopathology (USA), 1985. Google Scholar
  24. Jianguo Wang, Eric Lo, and Man Lung Yiu. Identifying the most connected vertices in hidden bipartite graphs using group testing. IEEE Transactions on Knowledge and Data Engineering, 25(10):2245-2256, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact