Paper Info
Title
A Complexity Dichotomy For Hypergraph Partition Functions
Abstract
We consider the complexity of counting homomorphisms from an r-uniform hypergraph G to a symmetric r-ary relation H. We give a dichotomy theorem for r > 2, showing for which H this problem is in FP and for which H it is #P-complete. This generalises a theorem of Dyer and Greenhill (2000) for the case r = 2, which corresponds to counting graph homomorphisms. Our dichotomy theorem extends to the case in which the relation H is weighted, and the goal is to compute the partition function, which is the sum of weights of the homomorphisms. This problem is motivated by statistical physics, where it arises as computing the partition function for particle models in which certain combinations of r sites interact symmetrically. In the weighted case, our dichotomy theorem generalises a result of Bulatov and Grohe (2005) for graphs, where r = 2. When r = 2, the polynomial time cases of the dichotomy correspond simply to rank-1 weights. Surprisingly, for all r > 2 the polynomial time cases of the dichotomy have rather more structure. It turns out that the weights must be superimposed on a combinatorial structure defined by solutions of an equation over an Abelian group. Our result also gives a dichotomy for a closely related constraint satisfaction problem.
Year
DOI
Venue
2008
10.1007/s00037-010-0300-6
Clinical Orthopaedics and Related Research
Keywords
DocType
Volume
dichotomy theorem,symmetric r-ary relation h.,weighted case,hypergraph partition functions,related constraint satisfaction problem,partition functions.,partition function,relation h,polynomial time case,. dichotomy,hypergraph,r sites interact symmetrically,complexity dichotomy,combinatorial structure,graph homomorphisms,Dichotomy,partition functions,68Q17,08A70,68Q25,68R05,68R10
Journal
19
Issue
ISSN
Citations 
4
1016-3328
9
PageRank 
References 
Authors
0.60
5
3
Name
Order
Citations
PageRank
Martin Dyer1102997.62
leslie ann goldberg21411125.20
mark jerrum32755564.62