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:
“Belonging to a group can provide the child with a variety of resources that an individual friendship often cannot—a sense of collective participation, experience with organizational roles, and group support in the enterprise of growing up. Groups also pose for the child some of the most acute problems of social life—of inclusion and exclusion, conformity and independence.”
—Zick Rubin (20th century)