Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-02-04T15:59:15.608Z Has data issue: false hasContentIssue false
  • English
  • Français

Satisfiability thresholds for regular occupation problems

Part of: Graph theory

Published online by Cambridge University Press:  04 February 2025

Konstantinos Panagiotou Open the ORCID record for Konstantinos Panagiotou [Opens in a new window]  and
Matija Pasch Open the ORCID record for Matija Pasch [Opens in a new window]
Konstantinos Panagiotou*
Affiliation:
LMU München, Munich, Germany
Matija Pasch
Affiliation:
LMU München, Munich, Germany
*
Corresponding author: Konstantinos Panagiotou; Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In the last two decades the study of random instances of constraint satisfaction problems (CSPs) has flourished across several disciplines, including computer science, mathematics and physics. The diversity of the developed methods, on the rigorous and non-rigorous side, has led to major advances regarding both the theoretical as well as the applied viewpoints. Based on a ceteris paribus approach in terms of the density evolution equations known from statistical physics, we focus on a specific prominent class of regular CSPs, the so-called occupation problems, and in particular on $r$-in-$k$ occupation problems. By now, out of these CSPs only the satisfiability threshold – the largest degree for which the problem admits asymptotically a solution – for the $1$-in-$k$ occupation problem has been rigorously established. Here we determine the satisfiability threshold of the $2$-in-$k$ occupation problem for all $k$. In the proof we exploit the connection of an associated optimization problem regarding the overlap of satisfying assignments to a fixed point problem inspired by belief propagation, a message passing algorithm developed for solving such CSPs.

Keywords

Occupation problemssatisfiability thresholdssecond moment methodsmall subgraph conditioningcontraction coefficientconfiguration model

MSC classification

Primary: 05C80: Random graphs
Type
Paper
Information
Combinatorics, Probability and Computing , First View , pp. 1 - 37
Check for updates
Copyright
© The Author(s), 2025. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abbe, E. (2018) Community detection and stochastic block models: recent developments. J Mach Learn Res 18 1–86.Google Scholar
Bahmanian, M. A. and Šajna, M. (2017) Quasi-Eulerian hypergraphs. Electron. J. Combin 24 12.CrossRefGoogle Scholar
Bapst, V., Coja-Oghlan, A. and Efthymiou, C. (2017) Planting colourings silently. Combin. Probab. Comput 26 338–366.CrossRefGoogle Scholar
Bollobás, B. (1980) A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin 1 311–316.CrossRefGoogle Scholar
Braunstein, A., Mézard, M. and Zecchina, R. (2005) Survey propagation: an algorithm for satisfiability. Random Struct. Algor. 27 201–226.CrossRefGoogle Scholar
Castellani, T., Napolano, V., Ricci-Tersenghi, F. and Zecchina, R. (2003) Bicolouring random hypergraphs. J. Phys. A 36 11037–11053.CrossRefGoogle Scholar
Coja-Oghlan, A. (2016) Constraint satisfaction: random regular k-SAT. In Statistical physics, optimization, inference, and message-passing algorithms. Oxford: Oxford Univ. Press, pp. 231–251.Google Scholar
Coja-Oghlan, A., Efthymiou, C., Jaafari, N., Kang, M. and Kapetanopoulos, T. (2018) Charting the replica symmetric phase. Comm. Math. Phys 359 603–698.CrossRefGoogle Scholar
Coja-Oghlan, A., Krzakala, F., Perkins, W. and Zdeborova, L. (2018) Information-theoretic thresholds from the cavity method. Adv. Math 333 694–795.CrossRefGoogle Scholar
Coja-Oghlan, A. and Panagiotou, K. (2016) The asymptotic k-SAT threshold. Adv. Math 288 985–1068.CrossRefGoogle Scholar
Cooper, C., Frieze, A., Molloy, M. and Reed, B. (1996) Perfect matchings in random r-regular, s-uniform hypergraphs. Combin. Probab. Comput 5 1–14.CrossRefGoogle Scholar
Dall’Asta, L., Ramezanpour, A. and Zecchina, R. (2008) Entropy landscape and non-Gibbs solutions in constraint satisfaction problems. Phys. Rev. E 77 031118, 16.CrossRefGoogle ScholarPubMed
Ding, J., Sly, A. and Sun, N. (2015) Proof of the satisfiability conjecture for large k . In STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing. ACM, New York, pp. 59–68.CrossRefGoogle Scholar
Ding, J., Sly, A. and Sun, N. (2016) Maximum independent sets on random regular graphs. Acta Math 217 263–340.CrossRefGoogle Scholar
Ding, J., Sly, A. and Sun, N. (2016) Satisfiability threshold for random regular NAE-SAT. Comm. Math. Phys 341 435–489.CrossRefGoogle Scholar
Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl 5 17–61.Google Scholar
Erdős, P. and Rényi, A. (1966) On the existence of a factor of degree one of a connected random graph. Acta Math. Acad. Sci. Hungar 17 359–368.CrossRefGoogle Scholar
Feige, U. (2002) Relations between average case complexity and approximation complexity. In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC ’02, ACM, New York, NY, USA, pp. 534–543,CrossRefGoogle Scholar
Frieze, A., Jerrum, M., Molloy, M., Robinson, R. W. and Wormald, N. C. (1996) Generating and counting Hamilton cycles in random regular graphs. J. Algorithms 21 176–198.CrossRefGoogle Scholar
Gabrié, M., Dani, V., Semerjian, G. and Zdeborová, L. (2017) Phase transitions in the q-coloring of random hypergraphs. J. Phys. A 50 44.CrossRefGoogle Scholar
Galanis, A., Štefankovič, D. and Vigoda, E. (2014) Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC ’14, New York, NY, USA, pp. 823–831,CrossRefGoogle Scholar
Higuchi, S. and Mézard, M. (2010) Correlation-based decimation in constraint satisfaction problems. J. Phys. Conf. Ser. 233 012003.CrossRefGoogle Scholar
Janson, S. (1995) Random regular graphs: asymptotic distributions and contiguity. Combin. Probab. Comput 4 369–405.CrossRefGoogle Scholar
Janson, S., Łuczak, T. and Rucinski, A. (2000) Random graphs. Wiley-Interscience, New York, Wiley-Interscience Series in Discrete Mathematics and Optimization.CrossRefGoogle Scholar
Kahn, J. (2022) Hitting times for Shamir’s problem. Trans. Amer. Math. Soc 375 627–668.CrossRefGoogle Scholar
Kalapala, V. and Moore, C. (2008) The phase transition in exact cover. Chic. J. Theoret. Comput. Sci. 5 9, pages Article.Google Scholar
Kemkes, G., Pérez-Giménez, X. and Wormald, N. C. (2010) On the chromatic number of random d-regular graphs. Adv. Math 223 300–328.CrossRefGoogle Scholar
Krzakala, F., Ricci-Tersenghi, F., Zdeborová, L., Zecchina, R., Tramel, E. W. and Cugliandolo, L. F. (2016) Statistical physics, optimization, inference, and message-passing algorithms, Oxford: Oxford University Press, editors.Google Scholar
Kudekar, S., Richardson, T. and Urbanke, R. (2013) Spatially coupled ensembles universally achieve capacity under belief propagation. IEEE Trans. Inform. Theory 59 7761–7813.CrossRefGoogle Scholar
Maneva, E., Mossel, E. and Wainwright, M. J. (2007) A new look at survey propagation and its generalizations. J. ACM 54 17.CrossRefGoogle Scholar
Mézard, M. and Montanari, A. (2009) Information, physics, and computation. Oxford University Press, Oxford. Oxford Graduate TextsCrossRefGoogle Scholar
Mézard, M., Parisi, G. and Virasoro, M. A. (1987) Spin glass theory and beyond. In World Scientific Lecture Notes in Physics, vol. 9, Teaneck, NJ: World Scientific Publishing Co., Inc.Google Scholar
Molloy, M., Robalewska, H. D., Robinson, R. W. and Wormald, N. C. (1997) 1-factorizations of random regular graphs. Random Structures Algorithms 10 305–321.3.0.CO;2-#>CrossRefGoogle Scholar
Moore, C. (2016) The phase transition in random regular exact cover. Ann. Inst. Henri Poincaré D 3 349–362.CrossRefGoogle Scholar
Mora, T. (2007) Geometry and Inference in Optimization and in Information Theory. Theses, Université Paris Sud - Paris XI.Google Scholar
Panagiotou, K. and Pasch, M. (2019) Satisfiability Thresholds for Regular Occupation Problems. In 46th Int. Col. on Automata, Languages, and Programming (ICALP ’19), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), 90:1–90:14.Google Scholar
Robalewska, H. D. (1996) 2-factors in random regular graphs. J. Graph Theory 23 215–224.3.0.CO;2-V>CrossRefGoogle Scholar
Robbins, H. (1955) A remark on Stirling’s formula. Amer. Math. Monthly 62 26–29.Google Scholar
Schmidt, C., Guenther, N. and Zdeborová, L. (2016) Circular coloring of random graphs: statistical physics investigation. J. Stat. Mech. Theory Exp 2016 083303, 28.CrossRefGoogle Scholar
Talagrand, M. (2003) Spin glasses: a challenge for mathematicians. volume 46 of Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics, Springer-Verlag, Berlin,Google Scholar
Yedidia, J. S., Freeman, W. T. and Weiss, Y. (2001) Bethe free energy, kikuchi approximations, and belief propagation algorithms, Technical Report TR2001-16, MERL - Mitsubishi Electric Research Laboratories, Cambridge, MA 02139, May 2001.Google Scholar
Zdeborová, L. and Krzakala, F. (2011) Quiet planting in the locked constraint satisfaction problems. SIAM J. Discrete Math 25 750–770.CrossRefGoogle Scholar
Zdeborová, L. and Mézard, M. (2008) Constraint satisfaction problems with isolated solutions are hard. J. Stat. Mech. Theory Exp 2008 P12004.CrossRefGoogle Scholar