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 mother’s and father’s attitudes toward the child correspond to the child’s own needs.... Mother has the function of making him secure in life, father has the function of teaching him, guiding him to cope with those problems with which the particular society the child has been born into confronts him.”
—Erich Fromm (1900–1980)