<p>For simplicity, let's restrict ourselves to $k$-regular graphs.</p>

<p>The first part of your update is correct.  Changing notation slightly from what you have introduced, let me define $n_e$ (resp. $n_o$) to be the number even (resp. odd) edge-induced subgraphs of a given graph $G$.  For the (arity $k$) signature $f = [1, -1, -1, \dotsc, -1]$, the Holant problem Holant($f$) does indeed correspond to the problem "Given a graph, compute $n_e - n_o$."  To see this, fix a subset of edges $E'$ (i.e. the subset of edges assigned 1) and consider a vertex $v$.  If none of the incident edges of $v$ are in $E'$, then $v$ is not in the edge-induced subgraph defined by $E'$ and the constraint at $v$ contributes a factor of 1 to the weight of $E'$.  Otherwise, some incident edge of $v$ is in $E'$, then $v$ is in the edge-induced subgraph defined by $E'$ and the constraint at $v$ contributes a $-1$ to the weight of $E'$.  Summing over the weights of all subsets of the edges gives $n_e - n_o$.  Since $n_e + n_o = 2^{|E(G)|}$, we could solve for $n_e$ and $n_o$ if we could knew $n_e - n_o$.</p>

<p>The second part of your update is incorrect.  The $k$-ary signature $f = [1, -1, -1, \dotsc, -1]$ is not affine for $k \ge 3$.  For a (rather explicit) list of the affine signatures, see page 7 of <a href="http://arxiv.org/abs/1204.6445" rel="nofollow">this paper</a>.  For $k \ge 3$, this signature defines a #P-hard Holant problem. To determine the complexity of this problem, notice that $f$ has the tensor rank 2 decomposition $f = 2 [1, 0]^{\otimes k} - [1,1]^{\otimes k}$. Let $\omega_{2k}$ be a $2k$th primitive root of unity. Then $f = [\sqrt[k]{2}, 0]^{\otimes k} + [\omega_{2k},\omega_{2k}]^{\otimes k}$.  Under a holographic transformation by the inverse of $M = \begin{bmatrix} \sqrt[k]{2} &amp; \omega_{2k} \\ 0 &amp; \omega_{2k} \end{bmatrix}$, we have the bipartite Holant problem $\operatorname{Holant}([\sqrt[k]{4}, \omega_{2k} \sqrt[k]{2}, 2 \omega_{2k}^2] | =_k)$.  This problem is #P-hard by Theorem 22 in <a href="http://cs.nmu.edu/~mkowalcz/research/main.pdf" rel="nofollow">this paper</a>, even when also restricting to planar graphs.</p>

<p>For $k \le 2$, $f$ is actually affine, so the problem is tractable, but it is also tractable for a much simpler reason as well.  Any Holant problem using only constraints of arity at most 2 is tractable using matrix product and trace.</p>

CC BY-SA 3.0
2013-05-12T08:57:54.723Z
Tyson, you said _"...fix $k=4$"_ which lead us to a #P-hard problem by Theorem 22 in Kowalczyk's paper. What about $k = 3$? I'm wondering if the signature $[1, -1, -1, -1]$ is affine-transformable (in the sense of Definition 3.1 in Huang and Lu paper). Finally, what is known about the complexity of computing the parity of $n_o$ in $3$-regular graphs or even in $2/3$-regular bipartite planar graphs? Thanks as usual for your very good answers.
Giorgio Camerani
CC BY-SA 3.0
2013-05-21T20:12:41.517Z
@GiorgioCamerani I have updated my answer to consider $k >= 3$. Not sure about parity. Look in "[The Complexity of Symmetric Boolean Parity Holant Problems](http://pages.cs.wisc.edu/~hguo/Papers/ParityHP.pdf)" by Heng Guo, Pinyan Lu, and Leslie G. Valiant for relevant papers.
Tyson Williams
CC BY-SA 3.0
2013-05-11T17:32:39.683Z
2013-05-21T23:27:42.600Z
2013-05-21T23:27:42.600Z
Tyson Williams
<p>Let $G$ be a graph. Let $O$ be the number of edge induced subgraphs of $G$ having an odd number of vertices.</p>

<blockquote>
  <p><strong>Questions</strong>  </p>
  
  <ol>
  <li>How hard is to compute $O$?</li>
  <li>How hard is to compute the parity of $O$? </li>
  </ol>
</blockquote>

<hr>

<p>Related questions:</p>

<ul>
<li><a href="https://cstheory.stackexchange.com/questions/12526/number-of-subgraphs-with-given-edge-parity">Number of (vertex induced) subgraphs with given edge parity</a> <strong>Answer</strong>: Tractable.</li>
<li><a href="https://cstheory.stackexchange.com/questions/12441/number-of-subgraphs-with-a-given-number-of-nodes">Number of (edge induced) subgraphs with a given number of nodes</a> <strong>Answer</strong>: #P-hard.</li>
</ul>

<hr>

<p><strong>Update 11/05/2013 18:00</strong>  </p>

<p>By a reasoning similar to the one in the answer to the first question referenced above, we can create a Holant by placing on each vertex $v$ a constraint $f_v$ which returns $1$ when all the edges incident to $v$ have been assigned $0$, and $-1$ otherwise. For a specific assignment to the edges ($0$ means not selected, $1$ means selected) we get an edge induced subgraph such that the number of its vertices is odd if and only if the product of the Holant returned $-1$. The summation of the Holant is thus equal to the difference $E - O$ between the number of edge induced subgraphs having an even number of vertices and the number of edge induced subgraphs having an odd number of vertices: as $E + O$ is known, we can determine $E$ and $O$.</p>

<p>Now, if I correctly understand the paper <a href="http://www.csc.kth.se/~sangxia/papers/2012-ccc.pdf" rel="nofollow noreferrer">A Dichotomy for Real Weighted Holant Problems</a>, the constraint $f_v$ is symmetric (obviously) and affine: by Theorem 3.2 this means that we can compute $E-O$ in polynomial time.</p>

<p>Am I right?</p>

<cc.complexity-theory><graph-theory><co.combinatorics><counting-complexity>
Number of edge induced subgraphs with given vertex parity
Giorgio Camerani
# Number of edge induced subgraphs with given vertex parity

(Asked by: username_0 on 2013-05-10)

Let $G$ be a graph. Let $O$ be the number of edge induced subgraphs of $G$ having an odd number of vertices.

> **Questions**
>
> 1. How hard is to compute $O$?
> 2. How hard is to compute the parity of $O$?

---

Related questions:

* [Number of (vertex induced) subgraphs with given edge parity](https://cstheory.stackexchange.com/questions/12526/number-of-subgraphs-with-given-edge-parity) **Answer**: Tractable.
* [Number of (edge induced) subgraphs with a given number of nodes](https://cstheory.stackexchange.com/questions/12441/number-of-subgraphs-with-a-given-number-of-nodes) **Answer**: #P-hard.

---

**Update 11/05/2013 18:00**

By a reasoning similar to the one in the answer to the first question referenced above, we can create a Holant by placing on each vertex $v$ a constraint $f\_v$ which returns $1$ when all the edges incident to $v$ have been assigned $0$, and $-1$ otherwise. For a specific assignment to the edges ($0$ means not selected, $1$ means selected) we get an edge induced subgraph such that the number of its vertices is odd if and only if the product of the Holant returned $-1$. The summation of the Holant is thus equal to the difference $E - O$ between the number of edge induced subgraphs having an even number of vertices and the number of edge induced subgraphs having an odd number of vertices: as $E + O$ is known, we can determine $E$ and $O$.

Now, if I correctly understand the paper [A Dichotomy for Real Weighted Holant Problems](http://www.csc.kth.se/~sangxia/papers/2012-ccc.pdf), the constraint $f\_v$ is symmetric (obviously) and affine: by Theorem 3.2 this means that we can compute $E-O$ in polynomial time.

Am I right?

**Tags:** cc.complexity-theory, graph-theory, co.combinatorics, counting-complexity

---

## 1 answers

### Answer by username_1 on 2013-05-11. Score: 4

For simplicity, let's restrict ourselves to $k$-regular graphs.

The first part of your update is correct. Changing notation slightly from what you have introduced, let me define $n\_e$ (resp. $n\_o$) to be the number even (resp. odd) edge-induced subgraphs of a given graph $G$. For the (arity $k$) signature $f = [1, -1, -1, \dotsc, -1]$, the Holant problem Holant($f$) does indeed correspond to the problem "Given a graph, compute $n\_e - n\_o$." To see this, fix a subset of edges $E'$ (i.e. the subset of edges assigned 1) and consider a vertex $v$. If none of the incident edges of $v$ are in $E'$, then $v$ is not in the edge-induced subgraph defined by $E'$ and the constraint at $v$ contributes a factor of 1 to the weight of $E'$. Otherwise, some incident edge of $v$ is in $E'$, then $v$ is in the edge-induced subgraph defined by $E'$ and the constraint at $v$ contributes a $-1$ to the weight of $E'$. Summing over the weights of all subsets of the edges gives $n\_e - n\_o$. Since $n\_e + n\_o = 2^{|E(G)|}$, we could solve for $n\_e$ and $n\_o$ if we could knew $n\_e - n\_o$.

The second part of your update is incorrect. The $k$-ary signature $f = [1, -1, -1, \dotsc, -1]$ is not affine for $k \ge 3$. For a (rather explicit) list of the affine signatures, see page 7 of [this paper](http://arxiv.org/abs/1204.6445). For $k \ge 3$, this signature defines a #P-hard Holant problem. To determine the complexity of this problem, notice that $f$ has the tensor rank 2 decomposition $f = 2 [1, 0]^{\otimes k} - [1,1]^{\otimes k}$. Let $\omega\_{2k}$ be a $2k$th primitive root of unity. Then $f = [\sqrt[k]{2}, 0]^{\otimes k} + [\omega\_{2k},\omega\_{2k}]^{\otimes k}$. Under a holographic transformation by the inverse of $M = \begin{bmatrix} \sqrt[k]{2} & \omega\_{2k} \\ 0 & \omega\_{2k} \end{bmatrix}$, we have the bipartite Holant problem $\operatorname{Holant}([\sqrt[k]{4}, \omega\_{2k} \sqrt[k]{2}, 2 \omega\_{2k}^2] | =\_k)$. This problem is #P-hard by Theorem 22 in [this paper](http://cs.nmu.edu/~mkowalcz/research/main.pdf), even when also restricting to planar graphs.

For $k \le 2$, $f$ is actually affine, so the problem is tractable, but it is also tractable for a much simpler reason as well. Any Holant problem using only constraints of arity at most 2 is tractable using matrix product and trace.

> **Comments:**
> **username_0**: Tyson, you said _"...fix $k=4$"_ which lead us to a #P-hard problem by Theorem 22 in Kowalczyk's paper. What about $k = 3$? I'm wondering if the signature $[1, -1, -1, -1]$ is affine-transformable (in the sense of Definition 3.1 in Huang and Lu paper). Finally, what is known about the complexity of computing the parity of $n_o$ in $3$-regular graphs or even in $2/3$-regular bipartite planar graphs? Thanks as usual for your very good answers.  
> **username_1**: @GiorgioCamerani I have updated my answer to consider $k >= 3$. Not sure about parity. Look in "[The Complexity of Symmetric Boolean Parity Holant Problems](http://pages.cs.wisc.edu/~hguo/Papers/ParityHP.pdf)" by Heng Guo, Pinyan Lu, and Leslie G. Valiant for relevant papers.  

---

