Large hypertree width for sparse random hypergraphs

摘要

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 -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.