User:Bender2k14/Holant

In theoretical computer science, the Holant is a function defined over instances of problems in the Holant framework. A problem in the Holant framework is defined by specifying a set of local constrain functions just as is done for a counting constraint satisfaction problem (#CSP). The Holant framework includes the #CSP framework as a special case, which in turn contains counting graph homomorphisms as a special case.

Many natural problems are expressible in the Holant framework. The framework is also important because it is conjectured that every problem it contains is either computable in polynomial time or is #P-hard. Theorems with this conclusion are called dichotomy theorems and have been proved for many special cases of the Holant framework.

Definition

A signature grid $\Omega =(G,{\mathcal {F}},\pi )$ is a tuple containing a graph $G=(V,E)$, a set ${\mathcal {F}}$ of functions (also called signatures) from [d]^k to a commutative semiring (or simply a field such as the complex numbers), and a mapping π that assigns to a vertex $v\in V$ a signature $\pi (v)=f_{v}$ from ${\mathcal {F}}$. An assignment σ from [d] to every edge $e\in E$ gives an evaluation

$w(\sigma )=\prod _{v\in V}f_{v}\left(\sigma \mid _{E(v)}\right),$

where E(v) denotes the incident edges of v and $\sigma \mid _{E(v)}$ denotes the restriction of $\sigma$ to E(v). Sometimes, this evaluation $w(\sigma )$ is also called the weight of the assignment $\sigma$.

Each set of signatures ${\mathcal {F}}$ defines a counting problem Holant$({\mathcal {F}})$. An instance of the counting problem is a signature grid Ω. The counting problem on the instance Ω is to compute the Holant function

$\operatorname {Holant} _{\Omega }=\sum _{\sigma :E\to [d]}\prod _{v\in V}f_{v}\left(\sigma \mid _{E(v)}\right).$

The term Holant was introduced by Leslie Valiant in his seminal work on holographic algorithms. The above definition for Holant, introduced by Cai, Lu, and Xia in 2008, is now standard.

Bipartite graphs

This definition has a slight generalization for bipartite graphs, which is particularly useful for expressing holographic algorithms.

For a bipartite graph $G=(U,V,E)$, the signature grid contains two sets of signatures ${\mathcal {F}}$ and ${\mathcal {G}}$, and the vertices in U are assigned signatures from ${\mathcal {F}}$ while the vertices in V are assigned signatures from ${\mathcal {G}}$. This bipartite Holant problem is expressed as Holant$({\mathcal {F}}\mid {\mathcal {G}})$, but the formal definition of the Holant function remains unchanged; it is still the sum over every assignment, the product over the signature evaluations at each vertex where the inputs to each signature are the values assigned to the incident edges of the vertex.

Specializations

Individual problems

Many classic counting problems have natural expressions in the Holant framework (or its bipartite variant), especially in the Boolean domain (where the assignments to the edges are one of two values, usually denoted by 0 and 1).

TODO:

• edge covers
• upset and downset (see also, antichain)
• #PL-CUT: given a planar graph G and a number k the problem is to compute the number of 2-colorings of the nodes of G such that exactly k edges have ends of opposite color (see Holographic Algorithms - Leslie G. Valiant [SIAM JoC])

Matchings

When the signature set ${\mathcal {F}}=\{\operatorname {AT-MOST-ONE} _{k}\mid k\in \mathbb {Z} ^{+}\}$ consists of the AT-MOST-ONE signature of every arity, the Holant function counts the number of matchings in the input graph. If the signature set ${\mathcal {F}}=\{\operatorname {EXACTLY-ONE} _{k}\mid k\in \mathbb {Z} ^{+}\}$ consists of the EXACT-ONE signatures of every arity, then the Holant function counts the number of perfect matchings in the input graph. Both of these counting problems are #P-complete over k-regular graphs for $k\geq 3$. Counting the number of matchings remains #P-complete even when the input graphs must also be planar, but counting the number of perfect matchings over planar graphs is tractable by the FKT algorithm.

Vertex covers and independent sets

In the bipartite variant, when ${\mathcal {F}}=\{\operatorname {OR} _{2}\}$ consists of the binary OR signature and ${\mathcal {G}}=\{=_{k}\mid k\in \mathbb {Z} ^{+}\}$ consists of the EQUALITY signatures of every arity, the Holant function applied to a bipartite graph $G=(V,U,E)$ counts the number of vertex covers in the graph with vertex set V and edge set $\{(u,v)\in V\times V\mid \operatorname {d} _{G}(u,v)=2\}.$ Basically each (degree two) vertex in U acts like an edge for its two neighboring vertices in V. Similarly, if ${\mathcal {F}}=\{\operatorname {NAND} _{2}\}$ and ${\mathcal {G}}=\{=_{k}\mid k\in \mathbb {Z} ^{+}\}$, then the Holant function counts the number of independent sets in the same implicit graph. Both of these counting problems are #P-complete even when restricted to planar k-regular graphs for $k\geq 3$.

Eulerian orientations

Another natural problem easily expressible as a bipartite Holant problem is counting the number of Eulerian orientations. This is the case when ${\mathcal {F}}=\{\neq _{2}\}$ consists of the binary DISEQUALITY signature and ${\mathcal {G}}=\{\operatorname {EXACTLY-HALF} _{2k}\mid k\in \mathbb {Z} ^{+}\}$ consists of the EXACTLY-HALF signatures of every even arity that are 1 when exactly half of the inputs are 1 and is 0 otherwise. The Eulerian orientations are being counted in the same implicit graph defined above. This time, the binary DISEQUALITY signature on the vertices in U gives an orientation to the edges represented by these vertices. This problem is #P-complete even when restricted to planar k-regular graphs for even $k\geq 4$ (REF: my paper with Heng).

Graph colorings

Graph coloring problems are naturally expressed as Holant problems with larger domains.

The problem of counting vertex colorings using d colors corresponds to the bipartite Holant problem on domain size d in which ${\mathcal {F}}=\{\neq _{2}\}$ consists of the binary DISEQUALTY signature and ${\mathcal {G}}=\{=_{k}\mid k\in \mathbb {Z} ^{+}\}$ consists of the EQUALITY signatures of every arity. The vertex colorings are being counted in the same implicit graph as defined above. This problem is also #P-complete, even when restricted to planar bipartite graphs (REF: Tutte polynomial), except for when d=2, in which case the problem is tractable even over general graphs.

The problem of counting edge colorings using d colors corresponds to the Holant problem with domain size d in which ${\mathcal {F}}=\{\operatorname {ALL-DISTINCT} _{k}\mid k\in \mathbb {Z} ^{+}\}$ consists of the ALL-DISTINCT signatures of every arity that are 1 when all the inputs are distinct and is 0 otherwise.

Counting constraint satisfaction problems

When The framework of counting constraint satisfaction problems (#CSP)

Research interests

By a generalization of Ladner's theorem, there are also problems in neither FP nor #P-complete as long as FP ≠ #P. (TODO cite paper here)

See also

• Tutte polynomial