Paul Beame
Sariel Har-Peled
Skip Abstract Section
Abstract
We study the task of estimating the number of edges in a graph, where the access to the graph is provided via 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, using (i) polylog(n) bipartite independent set queries or (ii) n2/3 polylog(n) independent set queries.
- Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee. 2018. Sublinear-time algorithms for counting star subgraphs via edge sampling. Algorithmica 80, 2 (2018), 668--697. DOI:https://doi.org/10.1007/s00453-017-0287-3Google Scholar
Digital Library
- Noga Alon and Vera Asodi. 2005. Learning a hidden subgraph. SIAM Journal on Discrete Mathematics 18, 4 (2005), 697–712.Google ScholarDigital Library
- Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. 2004. Learning a hidden matching. SIAM J. Comput. 33, 2 (2004), 487–501.Google ScholarDigital Library
- Dana Angluin and Jiang Chen. 2006. Learning a hidden hypergraph. Journal of Machine Learning Research 7, Oct. (2006), 2215–2236.Google Scholar
- Dana Angluin and Jiang Chen. 2008. Learning a hidden graph using O(log n) queries per edge. J. Comput. Syst. Sci. 74, 4 (June 2008), 546–556. DOI:https://doi.org/10.1016/j.jcss.2007.06.006Google ScholarDigital Library
- B. Aronov and S. Har-Peled. 2008. On approximating the depth and related problems. SIAM Journal on Computing 38, 3 (2008), 899--921. DOI:https://doi.org/10.1137/060669474Google ScholarDigital Library
- P. Beame, S. Har-Peled, S. Natarajan Ramamoorthy, C. Rashtchian, and M. Sinha. 2018. Edge estimation with independent set oracles. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), A. R. Karlin (Ed.). Leibniz International Proceedings in Informatics (LIPIcs), Vol. 94. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 38:1–38:21. DOI:https://doi.org/10.4230/LIPIcs.ITCS.2018.38Google Scholar
- I. Ben-Eliezer, T. Kaufman, M. Krivelevich, and D. Ron. 2013. Comparing the strength of query types in property testing: The case of -colorability. Computational Complexity 22, 1 (2013), 89--135. DOI:https://doi.org/10.1007/s00037-012-0048-2Google ScholarDigital Library
- Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. 2019. Hyperedge estimation using polylogarithmic subset queries. arxiv:1908.04196.Google Scholar
- Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra. 2019. Triangle estimation using tripartite independent set queries. In 30th International Symposium on Algorithms and Computations (ISAAC 2019), P. Lu and G. Zhang (Eds.). Leibniz International Proceedings in Informatics (LIPIcs), Vol. 149. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 19:1–19:17. DOI:https://doi.org/10.4230/LIPIcs.ISAAC.2019.19Google Scholar
- S. Cabello and M. Jejčič. 2015. Shortest paths in intersection graphs of unit disks. Computational Geometry 48, 4 (2015), 360--367. DOI:https://doi.org/10.1016/j.comgeo.2014.12.003Google ScholarDigital Library
- C. L. Chen and W. H. Swallow. 1990. Using group testing to estimate a proportion, and to test the binomial model. Biometrics 46, 4 (Dec. 1990), 1035--1046. DOI:https://doi.org/10.2307/2532446Google ScholarCross Ref
- Xi Chen, Amit Levi, and Erik Waingarten. 2020. Nearly optimal edge estimation with independent set queries. In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA’20). 2916--2935. DOI:https://doi.org/10.1137/1.9781611975994.177Google ScholarCross Ref
- F. Chung and L. Lu. 2006. Concentration inequalities and martingale inequalities: A survey. Internet Mathematics 3, 1 (2006), 79--127. https://projecteuclid.org:443/euclid.im/1175266369Google ScholarCross Ref
- Holger Dell and John Lapinskas. 2018. Fine-grained reductions from approximate counting to decision. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC’18). ACM, New York, NY, 281–288. DOI:https://doi.org/10.1145/3188745.3188920Google ScholarDigital Library
- Holger Dell, John Lapinskas, and Kitty Meeks. 2020. Approximately counting and sampling small witnesses using a colourful decision oracle. In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA’20). 2201–2211. DOI:https://doi.org/10.1137/1.9781611975994.135Google ScholarCross Ref
- R. Dorfman. 1943. The detection of defective members of large populations. Annals of Mathematical Statistics 14, 4 (Dec. 1943), 436--440. DOI:https://doi.org/10.1214/aoms/1177731363Google ScholarCross Ref
- D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press. http://www.cambridge.org/gb/knowledge/isbn/item2327542/.Google Scholar
- T. Eden, A. Levi, D. Ron, and C. Seshadhri. 2017. Approximately counting triangles in sublinear time. SIAM Journal on Computing 46, 5 (2017), 1603--1646. DOI:https://doi.org/10.1137/15M1054389Google ScholarCross Ref
- T. Eden, D. Ron, and C. Seshadhri. 2017. On approximating the number of -cliques in sublinear time. arxiv:cs.DS/1707.04858.Google Scholar
- T. Eden and W. Rosenbaum. 2018. On sampling edges almost uniformly. In 1st Symposium on Simplicity in Algorithms (SOSA 2018), R. Seidel (Ed.). OpenAccess Series in Informatics (OASIcs), Vol. 61. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 7:1–7:9. DOI:https://doi.org/10.4230/OASIcs.SOSA.2018.7Google Scholar
- M. Falahatgar, A. Jafarpour, A. Orlitsky, V. Pichapati, and A. T. Suresh. 2016. Estimating the number of defectives with group testing. In Proceedings of the IEEE International Symposium on Information Theory (ISIT’16). IEEE, Los Alamitos, CA, 1376--1380. DOI:https://doi.org/10.1109/ISIT.2016.7541524Google Scholar
- U. Feige. 2006. On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM Journal on Computing 35, 4 (2006), 964--984. DOI:https://doi.org/10.1137/s0097539704447304Google ScholarDigital Library
- A. V. Fishkin. 2003. Disk graphs: A short survey. In Proceedings of the 1st International Workshop on Approximation and Online Algorithms (WAOA’03). 260--264. DOI:https://doi.org/10.1007/978-3-540-24592-6_23Google Scholar
- O. Goldreich and D. Ron. 2008. Approximating average parameters of graphs. Random Structures 8 Algorithms 32, 4 (2008), 473--493. DOI:https://doi.org/10.1002/rsa.v32:4Google Scholar
- M. Gonen, D. Ron, and Y. Shavitt. 2011. Counting stars and other small subgraphs in sublinear-time. SIAM Journal on Discrete Mathematics 25, 3 (2011), 1365--1411. DOI:https://doi.org/10.1137/100783066Google ScholarCross Ref
- Vladimir Grebinski and Gregory Kucherov. 1998. Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping. Discrete Applied Mathematics 88, 1–3 (1998), 147–165.Google ScholarDigital Library
- R. J. Klein, C. Zeiss, E. Chew, J.-Y. Tsai, R. S. Sackler, C. Haynes, A. K. Henning, et al. 2005. Complement factor H polymorphism in age-related macular degeneration. Science 308, 5720 (2005), 385--389. DOI:https://doi.org/10.1126/science.1109557Google Scholar
- K. Onak, D. Ron, M. Rosen, and R. Rubinfeld. 2012. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 1123--1131. http://dl.acm.org/citation.cfm?id=2095116.2095204Google Scholar
- Lev Reyzin and Nikhil Srivastava. 2007. Learning and verifying graphs using queries with a focus on edge counting. In International Conference on Algorithmic Learning Theory. Springer, 285–297.Google ScholarDigital Library
- D. Ron and G. Tsur. 2016. The power of an example: Hidden set size approximation using group queries and conditional sampling. ACM Transactions on Computation Theory 8, 4 (2016), Article 15, 19 pages. DOI:https://doi.org/10.1145/2930657Google ScholarDigital Library
- C. Seshadhri. 2015. A simpler sublinear algorithm for approximating the triangle count. arxiv:cs.DS/1505.01927.Google Scholar
- L. Stockmeyer. 1983. The complexity of approximate counting (preliminary version). In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC’83). 118--126. DOI:https://doi.org/10.1145/800061.808740Google Scholar
- L. Stockmeyer. 1985. On approximation algorithms for #P. SIAM Journal on Computing 14, 4 (1985), 849--861. DOI:https://doi.org/10.1137/0214060Google ScholarCross Ref
- W. H. Swallow. 1985. Group testing for estimating infection rates and probabilities of disease transmission. Phytopathology 75, 8 (1985), 882. DOI:https://doi.org/10.1094/phyto-75-882Google ScholarCross Ref
- J. Wang, E. Lo, and M. L. Yiu. 2013. Identifying the most connected vertices in hidden bipartite graphs using group testing. IEEE Tranactions on Knowledge and Data Engineering 25, 10 (2013), 2245--2256. DOI:https://doi.org/10.1109/TKDE.2012.178Google ScholarDigital Library
Index Terms
- Edge Estimation with Independent Set Oracles
Recommendations
Nearly optimal edge estimation with independent set queries
SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete AlgorithmsWe study the problem of estimating the number of edges of an unknown, undirected graph G = ([n], E) with access to an independent set oracle. When queried about a subset S ⊆ [n] of vertices, the independent set oracle answers whether S is an independent ...
Independent dominating set problem revisited
An independent dominating set of a graph G is a subset D of V such that every vertex not in D is adjacent to at least one vertex of D and no two vertices in D are adjacent. The independent dominating set (IDS) problem asks for an independent dominating ...
Independent Feedback Vertex Set for $$P_5$$P5-Free Graphs
The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer $$k\ge 0$$ký0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices ...
Comments