Holant Problems
Holographic algorithms exist in the context of Holant problems, which generalize counting constraint satisfaction problems (#CSP). A #CSP instance is a hypergraph G=(V,E) called the constraint graph. Each hyperedge represents a variable and each vertex is assigned a constraint A vertex is connected to an hyperedge if the constraint on the vertex involves the variable on the hyperedge. The counting problem is to compute
which is a sum over all variable assignments, the product of every constraint, where the inputs to the constrain are the variables on the incident hyperedges of .
A Holant problem is like a #CSP except the input must be a graph, not a hypergraph. Restricting the class of input graphs in this way is indeed a generalization. Given a #CSP instance, replace each hyperedge e of size s with a vertex v of degree s with edges incident to the vertices contained in e. The constraint on v is the equality function of arity s. This identifies all of the variables on the edges incident to v, which is the same effect as the single variable on the hyperedge e.
In the context of Holant problems, the expression in (1) is called the Holant after a related exponential sum introduced by Valiant.
Read more about this topic: Holographic Algorithm
Famous quotes containing the word problems:
“The three great problems of this century, the degradation of man in the proletariat, the subjection of women through hunger, the atrophy of the child by darkness.”
—Victor Hugo (1802–1885)