Abstract
Hypertree width is a graph-theoretic parameter similar to treewidth. It has many equivalent characterizations and many applications. If the hypertree width of the constraint graphs of the instances of a constraint satisfaction problem is bounded by a constant, then the CSP is tractable In this paper, we show that with high probability, hypertree width is large on sparse random \(k\)-uniform hypergraphs. Our results provide further theoretical evidence on the hardness of some random constraint satisfaction problems, called Model RB and Model RD, around the satisfiability phase transition points.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adler I, Gottlob G, Grohe M (2007) Hypertree width and related hypergraph invariants. Eur J Comb 28:2167–2181
Cheeseman P, Kanefsky R, Taylor W (1991) Where the really hard problems are. IJCAI 1991:163–169
Chekuri C, Rajaraman A (2000) Conjunctive query containment revisited. Theor Comput Sci 239(2):211–229
Cook SA, Mitchell DG (1997) Finding hard instances of the satisfiability problem: a survey. In: DIMACS series, vol 35, pp 1–17
Dechter R (1992) Constraint networks. In: Encyclopedia of artificial intelligence, 2nd edn, vol 1, pp 276–285. Wiley, Chichester
Dechter R (2006) Tractable structures for constraint satisfaction problems. In: Rossi F, van Beek P, Walsh T (eds) Handbook of constraint programming. Elsevier, Amsterdam, pp 209–244
Dechter R, Pearl J (1989) Tree clustering for constraint networks. Artif Intell 38(3):353–366
Fan Y, Shen J (2011) On the phase transitions of random k-constraint satisfaction problems. Artif Intell 175:914–927
Fan Y, Shen J, Xu K (2012) A general model and thresholds for random constraint satisfaction problems. Artif Intell 193:1–17
Fu H, Huang K, Shiue C (2013) A note on optimal pebbling of hypercubes. J Comb Optim 25:597–601
Gao Y (2003) Phase transition of tractability in constraint satisfaction and Bayesian network inference. In: Proceedings of UAI, pp 265–271
Gao Y (2006) On the threshold of having a linear treewidth in random graphs. COCOON 2006:226–234
Gao Y (2012) Treewidth of Erdös–Rényi random graphs, random intersection graphs, and scale-free random graphs. Discrete Appl Math 160(4–5):566–578
Gao Y, Culberson J (2007) Consistency and random constraint satisfaction problems. J Artif Intell Res (JAIR) 28:517–557
Gottlob G, Leone N, Scarcello F (2000) A comparison of structural CSP decomposition methods. Artif Intell 124:243–282
Gottlob G, Leone N, Scarcello F (2001a) Hypertree decompositions: a survey. In: MFCS 2001, LNCS2136, pp 37–57
Gottlob G, Leone N, Scarcello F (2001b) The complexity of acyclic conjunctive queries. JACM 48(3):431–498
Gottlob G, Leone N, Scarcello F (2002) Hypertree decomposition and tractable queries. J Comput Syst Sci 64(3):579–627
Gyssens M, Paredaens J (1984) A decomposition methodology for cyclic databases. In: Gallaire H, Nicolas J-M, Minker J (eds) Advances in data base theory, vol 2. Plemum Press, New York, pp 85–122
Gyssens M, Jeavons PG, Cohen DA (1994) Decomposition constraint satisfaction problems using database techniques. Artif Intell 66(1):57–89
Haviland H (2013) Independent dominating sets in regular graphs. J Comb Optim 26:120–126
Hu S, Qi L (2012) Algebraic connectivity of an even uniform hypergraph. J Comb Optim 24:564–579
Jiang W, Liu T, Ren T, Xu K (2011) Two hardness results on feedback vertex sets. In: Proceedings of FAW-AAIM, LNCS 6681, pp 233–243
Kloks T (1994) Treewidth: computations and approximations. Springer, Berlin, pp 18, 55
Lee C, Lee J, Oum S (2012) Rank-width of random graphs. J Graph Theory 70(3):339–347
Liu CH, Chang GJ (2013) Roman domination on strongly chordal graphs. J Comb Optim 26:608–619
Liu T, Lin X, Wang C, Su K, Xu K (2011) Large hinge width on sparse random hypergraphs. IJCAI 2011:611–616
Mitchell DG, Selman B, Levesque HJ (1992) Hard and easy distributions of sat problems. In: Proceedings of AAAI, pp 459–465
Panda BS, Pradhan D (2013) Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs. J Comb Optim 26:770–785
Selman B, Mitchell DG, Levesque HJ (1996) Generating hard satisfiability problems. Artif Intell 81:17–29
Wang C, Liu T, Cui P, Xu K (2011) A note on treewidth in random graphs. In: COCOA 2011, LNCS 6831, pp 491–499
Xu K, Li W (2000) Exact phase transitions in random constraint satisfaction problems. J Artif Intell Res 12:93–103
Xu K, Li W (2006) Many hard examples in exact phase transitions. Theor Comput Sci 355:291–302
Xu K, Boussemart F, Hemery F, Lecoutre C (2007) Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif Intell 171:514–534
Zhao C, Zhang P, Zheng Z, Xu K (2012) Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains. Phys Rev E 85:016106
Acknowledgments
We thank Professor Kaile Su for his encouragement and support. We also thank the unknown referees for helpful comments. Partially supported by National 973 Program of China (Grant No. 2010CB328103) and Natural Science Foundation of China (Grant Nos. 61370156 and 61370052).
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Liu, T., Wang, C. & Xu, K. Large hypertree width for sparse random hypergraphs. J Comb Optim 29, 531–540 (2015). https://doi.org/10.1007/s10878-013-9704-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-013-9704-y