Computer Science – Computational Complexity
Scientific paper
2008-10-31
Computer Science
Computational Complexity
21 pages
Scientific paper
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 \emph{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.
Dyer Martin
Goldberg Leslie Ann
Jerrum Mark
No associations
LandOfFree
A complexity dichotomy for hypergraph partition functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A complexity dichotomy for hypergraph partition functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A complexity dichotomy for hypergraph partition functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-381673