Document Open Access Logo

Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs

Authors Ewan Davies , Will Perkins

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.62.pdf
  • Filesize: 0.79 MB
  • 18 pages

Document Identifiers

Author Details

Ewan Davies
  • Department of Computer Science, University of Colorado, Boulder, CO, USA
Will Perkins
  • Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, IL, USA

Funding

  • Perkins, Will: supported in part by NSF grants DMS-1847451 and CCF-1934915.

Cite As Get BibTex

Ewan Davies and Will Perkins. Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 62:1-62:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.62

Abstract

We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density α_c(Δ) and provide (i) for α < α_c(Δ) randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most α n in n-vertex graphs of maximum degree Δ; and (ii) a proof that unless NP=RP, no such algorithms exist for α > α_c(Δ). The critical density is the occupancy fraction of hard core model on the clique K_{Δ+1} at the uniqueness threshold on the infinite Δ-regular tree, giving α_c(Δ) ~ e/(1+e)1/(Δ) as Δ → ∞.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Mathematics of computing → Approximation algorithms
  • Theory of computation → Algorithm design techniques
  • Theory of computation → Random walks and Markov chains
Keywords
  • approximate counting
  • independent sets
  • Markov chains

Metrics

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

Related Versions

References

  1. Vedat Levi Alev and Lap Chi Lau. Improved analysis of higher order random walks and applications. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1198-1211, Chicago IL USA, 2020. ACM. URL: https://doi.org/10.1145/3357713.3384317.
  2. N. Anari, K. Liu, and S. O. Gharan. Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1319-1330, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00125.
  3. Alexander Barvinok. Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and Combinatorics. Springer International Publishing, Cham, 2016. URL: https://doi.org/10.1007/978-3-319-51829-9.
  4. Nayantara Bhatnagar, Allan Sly, and Prasad Tetali. Decay of correlations for the hardcore model on the d-regular random graph. Electronic Journal of Probability, 21(0), 2016. URL: https://doi.org/10.1214/16-EJP3552.
  5. R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 223-231, Miami Beach, FL, USA, 1997. IEEE Comput. Soc. URL: https://doi.org/10.1109/SFCS.1997.646111.
  6. Z. Chen, K. Liu, and E. Vigoda. Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1307-1318, November 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00124.
  7. Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion. CoRR, 2020. URL: http://arxiv.org/abs/2011.02075.
  8. Radu Curticapean, Holger Dell, Fedor Fomin, Leslie Ann Goldberg, and John Lapinskas. A fixed-parameter perspective on #BIS. Algorithmica, 81(10):3844-3864, 2019. Google Scholar
  9. Jonathan Cutler and A.J. Radcliffe. The maximum number of complete subgraphs in a graph with given maximum degree. Journal of Combinatorial Theory, Series B, 104:60-71, 2014. URL: https://doi.org/10.1016/j.jctb.2013.10.003.
  10. Ewan Davies, Matthew Jenssen, and Will Perkins. A proof of the Upper Matching Conjecture for large graphs. CoRR, April 2020. URL: http://arxiv.org/abs/2004.06695.
  11. Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts. On the average size of independent sets in triangle-free graphs. Proc. Amer. Math. Soc., 146(1):111-124, 2017. URL: https://doi.org/10.1090/proc/13728.
  12. Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts. Tight bounds on the coefficients of partition functions via stability. Journal of Combinatorial Theory, Series A, 160:1-30, November 2018. URL: https://doi.org/10.1016/j.jcta.2018.06.005.
  13. Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3):471-500, 2004. URL: https://doi.org/10.1007/978-3-642-04016-0.
  14. Talya Eden, Dana Ron, and C. Seshadhri. On Approximating the Number of k-Cliques in Sublinear Time. SIAM Journal on Computing, 49(4):747-771, January 2020. URL: https://doi.org/10.1137/18M1176701.
  15. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326(1):57-67, 2004. URL: https://doi.org/10.1016/j.tcs.2004.05.009.
  16. Andreas Galanis, Daniel Stefankovič, and Eric Vigoda. Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models. Combinatorics, Probability and Computing, 25(4):500-559, July 2016. URL: https://doi.org/10.1017/S0963548315000401.
  17. B. V. Gnedenko. On a local limit theorem of the theory of probability. Uspehi Matem. Nauk (N. S.), 3(3(25)):187-194, 1948. Google Scholar
  18. C. Greenhill. The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Comput. complex., 9(1):52-72, November 2000. URL: https://doi.org/10.1007/PL00001601.
  19. David G. Harris and Vladimir Kolmogorov. Parameter estimation for Gibbs distributions. CoRR, 2021. URL: http://arxiv.org/abs/2007.10824.
  20. Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM Journal on Computing, 18(6):1149-1178, 1989. Google Scholar
  21. Mark Jerrum and Alistair Sinclair. Polynomial-Time Approximation Algorithms for the Ising Model. SIAM Journal on Computing, 22(5):1087-1116, October 1993. URL: https://doi.org/10.1137/0222066.
  22. Mark Jerrum and Alistair Sinclair. The Markov chain Monte Carlo method: An approach to approximate counting and integration. In Approximation Algorithms for NP-Hard Problems. PWS Pub. Co, 1997. Google Scholar
  23. F. P. Kelly. Stochastic Models of Computer Communication Systems. Journal of the Royal Statistical Society. Series B (Methodological), 47(3):379-395, 1985. Google Scholar
  24. J.L. Lebowitz, B. Pittel, D. Ruelle, and E.R. Speer. Central limit theorems, LeeendashYang zeros, and graph-counting polynomials. Journal of Combinatorial Theory, Series A, 141:147-183, July 2016. URL: https://doi.org/10.1016/j.jcta.2016.02.009.
  25. Marcus Michelen and Julian Sahasrabudhe. Central limit theorems and the geometry of polynomials. CoRR, 2019. URL: http://arxiv.org/abs/1908.09020.
  26. Marcus Michelen and Julian Sahasrabudhe. Central limit theorems from the roots of probability generating functions. Advances in Mathematics, 358:106840, December 2019. URL: https://doi.org/10.1016/j.aim.2019.106840.
  27. Viresh Patel and Guus Regts. Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials. SIAM J. Comput., 46(6):1893-1919, January 2017. URL: https://doi.org/10.1137/16M1101003.
  28. Han Peters and Guus Regts. On a Conjecture of Sokal Concerning Roots of the Independence Polynomial. Michigan Math. J., 68(1):33-55, April 2019. URL: https://doi.org/10.1307/mmj/1541667626.
  29. Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93-133, July 1989. URL: https://doi.org/10.1016/0890-5401(89)90067-9.
  30. Allan Sly. Computational Transition at the Uniqueness Threshold. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 287-296, Las Vegas, NV, USA, October 2010. IEEE. URL: https://doi.org/10.1109/FOCS.2010.34.
  31. Allan Sly and Nike Sun. Counting in two-spin models on d-regular graphs. Ann. Probab., 42(6):2383-2416, November 2014. URL: https://doi.org/10.1214/13-AOP888.
  32. Leslie G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM J. Comput., 8(3):410-421, August 1979. URL: https://doi.org/10.1137/0208032.
  33. Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing - STOC '06, page 140, Seattle, WA, USA, 2006. ACM Press. URL: https://doi.org/10.1145/1132516.1132538.
  34. Yufei Zhao. Extremal regular graphs: independent sets and graph homomorphisms. The American Mathematical Monthly, 124(9):827-843, 2017. URL: https://doi.org/10.4169/amer.math.monthly.124.9.827.
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