<p>This topic has been extensively investigated in recent years under the name of <a href="http://en.wikipedia.org/wiki/Holographic_algorithm">Holographic Algorithms</a> by researchers such as Valiant, Cai, Lu, Xia, Lipton, and others. Essentially all tractable cases of #CSP (counting constraint satisfaction problems) have been identified in terms of dichotomy theorems (FP vs. #P-complete). In particular, Matchgate computations have been identified as the specific class of counting problems that become tractable on <em>planar</em> graphs. See e.g. this <a href="http://pages.cs.wisc.edu/~jyc/papers/planar.pdf">link</a> for further references.</p>

CC BY-SA 3.0
2012-02-09T18:59:28.970Z
Thank you Martin for the answer. The paper you linked is worth to read anyway. However, it does not mention a relationship of the form $\Phi \rightarrow A \rightarrow G$. The matrix $A$ nor its bipartite double cover graph $G$ are random, but depend entirely on the structure of $\Phi$ and the used graph gadgets. So the question is more on the classification of formulas $\Phi$ that lead to planar graphs $G$ and which not. (There are indeed formulas that will be planar, since we implemented the whole algorithm)
Etsch
CC BY-SA 3.0
2012-02-09T17:47:18.003Z
2012-02-09T17:47:18.003Z
Martin Schwarz
<p>Normally an unweighted #CSP problem is defined by a set of relations $\Gamma$ and the input to the problem #CSP($\Gamma$) is a formula $\Phi$.</p>

<p>If $\Gamma$ only contains relations of arity at most 1, then every possible input $\Phi$ correspondes to a graph with disjoint star graphs, which is planar. Furhtermore, if $\Gamma$ contains a relation of arity 2 or more, then it is easy to construt instantces that are not planar. (Think of the variables as the vertices of a graph and binary constraints as edges between these variables vertices. Higher arity contains also work. In this way, any graph can be constructed, as least as a subgraph of another graph.)</p>

<p>In constrast, you are ignoring $\Gamma$ and directly asking about which $\Phi$ lead to planar graphs. However, each $\Phi$ defines a (unique) graph. There is no uncertianity as you suggest in this paragraph:</p>

<blockquote>
  <p>Since the embedding of $G$ depends heavily on the formula $\Phi$, the hope is, that there exists certain formulas that lead more often into planar bipartite covers. Does anyone know if it has ever been investigated how large the chances are that $G$ will be planar?</p>
</blockquote>

CC BY-SA 3.0
2012-02-16T18:10:18.550Z
2012-02-16T23:04:24.700Z
2012-02-16T23:04:24.700Z
Tyson Williams
<p>In the paper of Ben-Dor/Halevi [1] it is given another proof that the permanent is
$\#P$-complete. In the later part of the paper, they show the reduction chain
\begin{equation}
\text{IntPerm} \propto \text{NoNegPerm} \propto \text{2PowersPerm} \propto \text{0/1-Perm}
\end{equation}
while the permanent value is preserved along the chain. Since the number of satiesfying assignments of a 3SAT formula $\Phi$ can be obtained from the permanent value, it is sufficient to compute the permanent of the final $0/1$-matrix. So far so good. </p>

<p>However, it is well known that the permanent of a $0/1$-matrix $\text{A}$ is equal to the number of perfect matchings in the bipartite double cover $G$, i.e., the graph from the matrix $\begin{pmatrix} 0 &amp; \text{A} \\ 
\text{A}^t &amp; 0 \end{pmatrix}$. And this number can be computed efficiently if $G$ turns out to be planar (using Kastelyens algorithm). </p>

<p>So in total this means, someone could compute the number of satiesfying assignments of a boolean formula $\Phi$ if the final graph $G$ is planar. </p>

<p><em>Since the embedding of $G$ depends heavily on the formula $\Phi$, the hope is, that there exists certain formulas that lead more often into planar bipartite covers.
Does anyone know if it has ever been investigated how large the chances are that $G$ will be planar?</em></p>

<p>Since counting satiesfying solutions is $\#P$-complete, the graphs will be for sure almost always non-planar, but i can not find any hints regarding this topic.</p>

<p>[1] <em>Amir Ben-Dor and Shai Halevi. Zero-one permanent is #p-complete, a simpler proof. In 2nd Israel Symposium on Theory of Computing Systems, pages 108-117, 1993. Natanya, Israel.</em></p>

<cc.complexity-theory><counting-complexity><permanent>
A question to the #P-complete proof of the permanent from Ben-Dor/Halevi
Etsch
# A question to the #P-complete proof of the permanent from Ben-Dor/Halevi

(Asked by: username_0 on 2012-02-09)

In the paper of Ben-Dor/Halevi [1] it is given another proof that the permanent is
$\#P$-complete. In the later part of the paper, they show the reduction chain
\begin{equation}
\text{IntPerm} \propto \text{NoNegPerm} \propto \text{2PowersPerm} \propto \text{0/1-Perm}
\end{equation}
while the permanent value is preserved along the chain. Since the number of satiesfying assignments of a 3SAT formula $\Phi$ can be obtained from the permanent value, it is sufficient to compute the permanent of the final $0/1$-matrix. So far so good.

However, it is well known that the permanent of a $0/1$-matrix $\text{A}$ is equal to the number of perfect matchings in the bipartite double cover $G$, i.e., the graph from the matrix $\begin{pmatrix} 0 & \text{A} \\
\text{A}^t & 0 \end{pmatrix}$. And this number can be computed efficiently if $G$ turns out to be planar (using Kastelyens algorithm).

So in total this means, someone could compute the number of satiesfying assignments of a boolean formula $\Phi$ if the final graph $G$ is planar.

*Since the embedding of $G$ depends heavily on the formula $\Phi$, the hope is, that there exists certain formulas that lead more often into planar bipartite covers.
Does anyone know if it has ever been investigated how large the chances are that $G$ will be planar?*

Since counting satiesfying solutions is $\#P$-complete, the graphs will be for sure almost always non-planar, but i can not find any hints regarding this topic.

[1] *Amir Ben-Dor and Shai Halevi. Zero-one permanent is #p-complete, a simpler proof. In 2nd Israel Symposium on Theory of Computing Systems, pages 108-117, 1993. Natanya, Israel.*

**Tags:** cc.complexity-theory, counting-complexity, permanent


---

## 2 answers

### Answer by username_1 on 2012-02-09. Score: 11

This topic has been extensively investigated in recent years under the name of [Holographic Algorithms](http://en.wikipedia.org/wiki/Holographic_algorithm) by researchers such as Valiant, Cai, Lu, Xia, Lipton, and others. Essentially all tractable cases of #CSP (counting constraint satisfaction problems) have been identified in terms of dichotomy theorems (FP vs. #P-complete). In particular, Matchgate computations have been identified as the specific class of counting problems that become tractable on *planar* graphs. See e.g. this [link](http://pages.cs.wisc.edu/~jyc/papers/planar.pdf) for further references.

> **Comments:**
> **username_0**: Thank you Martin for the answer. The paper you linked is worth to read anyway. However, it does not mention a relationship of the form $\Phi \rightarrow A \rightarrow G$. The matrix $A$ nor its bipartite double cover graph $G$ are random, but depend entirely on the structure of $\Phi$ and the used graph gadgets. So the question is more on the classification of formulas $\Phi$ that lead to planar graphs $G$ and which not. (There are indeed formulas that will be planar, since we implemented the whole algorithm)  

---

### Answer by username_2 on 2012-02-16. Score: 2

Normally an unweighted #CSP problem is defined by a set of relations $\Gamma$ and the input to the problem #CSP($\Gamma$) is a formula $\Phi$.

If $\Gamma$ only contains relations of arity at most 1, then every possible input $\Phi$ correspondes to a graph with disjoint star graphs, which is planar. Furhtermore, if $\Gamma$ contains a relation of arity 2 or more, then it is easy to construt instantces that are not planar. (Think of the variables as the vertices of a graph and binary constraints as edges between these variables vertices. Higher arity contains also work. In this way, any graph can be constructed, as least as a subgraph of another graph.)

In constrast, you are ignoring $\Gamma$ and directly asking about which $\Phi$ lead to planar graphs. However, each $\Phi$ defines a (unique) graph. There is no uncertianity as you suggest in this paragraph:

> Since the embedding of $G$ depends heavily on the formula $\Phi$, the hope is, that there exists certain formulas that lead more often into planar bipartite covers. Does anyone know if it has ever been investigated how large the chances are that $G$ will be planar?


---

