Large hypertree width for sparse random hypergraphs

Tian Liu (), Chaoyi Wang and Ke Xu ()
Additional contact information
Tian Liu: Peking University
Chaoyi Wang: Peking University
Ke Xu: Beihang University

Journal of Combinatorial Optimization, 2015, vol. 29, issue 3, No 2, 540 pages

Abstract: 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$$ 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.

Keywords: Constraint satisfaction; Random hypergraph; Hypertree width; Model RB; Model RD (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9704-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:3:d:10.1007_s10878-013-9704-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9704-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().