Abstract
Two models of nearly balanced random constraint satisfaction problems, called Model NB and UB respectively, are defined in this paper. By nearly balanced it means that most variables appear in the same number of constraints. Exact satisfiability thresholds for these models are proven, which are of the same values as that for Model RB. Experiments on random instances around the thresholds for these three models are conducted. The results show that these balanced models are much harder to solve than their unbalanced counterpart.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Achlioptas, D., Molloy, M., Kirousis, L., Stamatiou, Y., Kranakis, E., Krizanc, D.: Random constraint satisfaction: a more accurate picture. Constraints 6(4), 329–344 (2001)
Ansótegui, C., Béjar, R., Fernández, C., Gomes, C.P., Mateu, C.: The impact of balancing on problem hardness in a highly structured domain. In: Proceedings of AAAI, pp. 10–15 (2016)
Ansótegui, C., Béjar, R., Fernández, C., Gomes, C.P., Mateu, C.: Generating highly balanced sudoku problems as hard problems. J. Heuristics 17(5), 589–614 (2011)
Ansótegui, C., Béjar, R., Fernàndez, C., Mateu, C.: On balanced CSPs with high treewidth. In: Proceedings of AAAI, vol. 1, pp. 161–166 (2007)
Bollobás, B.: Random Graphs. Cambridge Studies in Advanced Mathematics (2001)
Cheeseman, P., Kanefsky, R., Taylor, W.: Where the really hard problems are. In: Proceedings of IJCAI, pp. 163–169 (1991)
Cook, S.A., Mitchell, D.G.: Finding hard instances of the satisfiability problem: a survey. In: Proceedings of SAT. DIMACS Series, vol. 35, pp. 1–17 (1997)
Creignou, N., Daudé, H.: Random generalized satisfiability problems. In: Proceedings of SAT, pp. 17–26 (2002)
Creignou, N., Daudé, H.: Generalized satisfiability problems: minimal elements and phase transitions. Theor. Comput. Sci. 302(1–3), 417–430 (2003)
Creignou, N., Daudé, H.: Combinatorial sharpness criterion and phase transition classification for random CSPs. Inf. Comput. 190(2), 220–238 (2004)
Fan, Y., Shen, J.: On the phase transitions of random \(k\)-constraint satisfaction problems. Artif. Intell. 175(3–4), 914–927 (2011)
Fan, Y., Shen, J., Xu, K.: A general model and thresholds for random constraint satisfaction problems. Artif. Intell. 193, 1–17 (2012)
Friedgut, E.: Sharp thresholds of graph properties, and the \(k\)-sat problem. J. Am. Math. Soc. 12, 1017–1054 (1998)
Friedgut, E.: Hunting for sharp thresholds. Random Struct. Algorithms 26(1–2), 37–51 (2005)
Frieze, A.M., Molloy, M.: The satisfiability threshold for randomly generated binary constraint satisfaction problems. Random Struct. Algorithms 28(3), 323–339 (2006)
Gao, Y., Culberson, J.: Consitency and random constraint satisfaction problems. J. Artif. Intell. Res. 28, 517–557 (2007)
Gent, I.P., Macintyre, E., Prosser, P., Smith, B.M.: Random constraint satisfaction: flaws and structure. Constraints 6, 345–372 (2001)
Gomes, C., Walsh, T.: Randomness and structures. Handbook of Constraint Programming, pp. 639–664 (2006)
Liu, T., Lin, X., Wang, C., Su, K., Xu, K.: Large hinge width on sparse random hypergraphs. In: Proceedings of IJCAI, pp. 611–616 (2011)
Mitchell, D.G., Selman, B., Levesque, H.J. : Hard and easy distributions of SAT problems. In: Proceedings of AAAI, pp. 459–465 (1992)
Molloy, M.: Models for random constraint satisfaction problems. SIAM J. Comput. 32(4), 935–949 (2003)
Prosser, P.: An empirical study of phase transitions in binary constraint satisfaction problems. Artif. Intell. 81(1–2), 81–109 (1996)
Selman, B., Mitchell, D.G., Levesque, H.J.: Generating hard satisfiability problems. Artif. Intell. 81(1–2), 17–29 (1996)
Smith, B.M., Dyer, M.E.: Locating the phase transition in binary constraint satisfaction problems. Artif. Intell. 81(1–2), 155–181 (1996)
Smith, B.: Constructing an asymptotic phase transition in random binary constraint satisfaction problems. Theor. Comput. Sci. 265, 265–283 (2001)
Xu, K.: BHOSLIB: Benchmarks with Hidden Optimum Solutions for Graph Problems. http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm
Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif. Intell. 171, 514–534 (2007)
Xu, K., Li, W.: Exact phase transitions in random constraint satisfaction problems. J. Artif. Intell. Res. 12, 93–103 (2000)
Xu, K., Li, W.: Many hard examples in exact phase transitions. Theor. Comput. Sci. 355(3), 291–302 (2006)
Acknowledgments
We thank Prof. Ke Xu for suggestions on doing this work and for many helpful discussions. This work was partially supported by Natural Science Foundation of China (Grant Nos. 61370052 and 61370156) and Fundamental Research Funds for the Central Universities (Grant No. FRF-TP-16-065A1).
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Liu, T., Wang, C., Xu, W. (2018). Balanced Random Constraint Satisfaction: Phase Transition and Hardness. In: Chen, J., Lu, P. (eds) Frontiers in Algorithmics. FAW 2018. Lecture Notes in Computer Science(), vol 10823. Springer, Cham. https://doi.org/10.1007/978-3-319-78455-7_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-78455-7_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-78454-0
Online ISBN: 978-3-319-78455-7
eBook Packages: Computer ScienceComputer Science (R0)