Abstract
Model RB is a random constraint satisfaction problem with a growing domain size, which exhibits exact phase transition phenomena. Many hard instances with planted solutions can be generated via Model RB, to be used as benchmarks for algorithmic competitions and researches. In the past, some structural parameters of constraint hypergraphs are analyzed to show hardness of Model RB, such as hinge width, decycling number, treewidth, and hypertree width. In this paper, one more structural parameter of constraint hypergraphs of Model RB, namely the fractional edge cover number, is analyzed. We show upper and lower bounds on the fractional edge cover number of Model RB. In particular, the fractional edge cover number of Model RB is shown to be asymptotically linear in the number of variables, like hinge width, decycling number, treewidth and hypertree width. These results together provide further evidences on the hardness of Model RB.
Partially supported by Natural Science Foundation of China (Grant Nos. 61370052 and 61370156).
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
Adler, I., Gottlob, G., Grohe, M.: Hypertree width and related hypergraph invariants. Eur. J. Comb. 28, 2167–2181 (2007)
Cheeseman, P., Kanefsky, R., Taylor, W.: Where the really hard problems are. In: Proceedings of IJCAI 1991, pp. 163–169 (1991)
Cook, S.A., Mitchell, D.G.: Finding hard instances of the satisfiability problem: a survey. DIMACS Ser. 35, 1–17 (1997)
Dubois, O., Boufkhad, Y., Mandler, J.: Typical random 3-SAT formulae and the satisfiability threshold. In: Proceedings of SODA 2000, pp. 126–127 (2000)
Fan, Y., Shen, J.: On the phase transitions of random \(k\)-constraint satisfaction problems. Artif. Intell. 175, 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)
Gao, Y.: Phase transition of tractability in constraint satisfaction and Bayesian network inference. In: Proceedings of UAI, pp. 265–271 (2003)
Gao, Y.: On the threshold of having a linear treewidth in random graphs. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 226–234. Springer, Heidelberg (2006)
Gao, Y.: Treewidth of Erdos-Renyi random graphs, random intersection graphs, and scale-free random graphs. Discrete Appl. Math. 160(4–5), 566–578 (2012)
Gao, Y., Culberson, J.: Consistency and random constraint satisfaction problems. J. Artif. Intell. Res. 28, 517–557 (2007)
Grohe, M., Marx, D.: Constraint solving via fractional edge covers. ACM Trans. Alg. 11(1), Article 4 (2014)
Jiang, W., Liu, T., Ren, T., Xu, K.: Two hardness results on feedback vertex sets. In: Atallah, M., Li, X.-Y., Zhu, B. (eds.) FAW-AAIM 2011. LNCS, vol. 6681, pp. 233–243. Springer, Heidelberg (2011)
Kloks, T.: Treewidth: Computations and Approximations, pp. 18–55. Springer, Berlin (1994)
Lee, C., Lee, J., Oum, S.: Rank-width of random graphs. J. Graph. Theor. 70(3), 339–347 (2012)
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)
Liu, T., Wang, C., Xu, K.: Large hypertree width for sparse random hypergraphs. J. Comb. Optim. 29, 531–540 (2015)
Marx, D.: Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM 60(6), 42 (2013)
Mezard, M., Parisi, G., Zecchina, R.: Analytic and algorithmic solution of random satisfiability problems. Science 297(5582), 812–815 (2002)
Mitchell, D.G., Selman, B., Levesque, H.J.: Hard and easy distributions of sat problems. In: Proceedings of AAAI 1992, pp. 459–465 (1992)
Selman, B., Mitchell, D.G., Levesque, H.J.: Generating hard satisfiability problems. Artif. Intell. 81, 17–29 (1996)
Rucinski, A., Janson, S., Luczak, T.: Random Graphs. Wiley, New York (2000)
Wang, C., Liu, T., Cui, P., Xu, K.: A note on treewidth in random graphs. In: Wang, W., Zhu, X., Du, D.-Z. (eds.) COCOA 2011. LNCS, vol. 6831, pp. 491–499. Springer, Heidelberg (2011)
Xu, K., Li, W.: Exact phase transitions in random constraint satisfaction problems. J. Artif. Intell. Res. 12, 93–103 (2000)
Xu, K.: BHOSLIB: Benchmarks with Hidden Optimum Solutions for Graph Problems. http://www.nlsde.buaa.edu.cn/kexu/benchmarks/graph-benchmarks.htm
Xu, K., Li, W.: Many hard examples in exact phase transitions. Theor. Comput. Sci. 355, 291–302 (2006)
Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif. Intell. 171, 514–534 (2007)
Xu, W., Zhang, P., Liu, T., Gong, F.: The solution space structure of random constraint satisfaction problems with growing domains. J. Stat. Mech. Theor. Exp. 2015, P12006 (2015)
Zhao, C., Zhang, P., Zheng, Z., Xu, K.: Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains. Phys. Rev. E 85, 016106 (2012)
Acknowledgments
We thank Ms. Yu Song for drafting an earlier version of this paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Liu, T. (2016). Fractional Edge Cover Number of Model RB. In: Zhu, D., Bereg, S. (eds) Frontiers in Algorithmics. FAW 2016. Lecture Notes in Computer Science(), vol 9711. Springer, Cham. https://doi.org/10.1007/978-3-319-39817-4_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-39817-4_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-39816-7
Online ISBN: 978-3-319-39817-4
eBook Packages: Computer ScienceComputer Science (R0)