Number of edge induced subgraphs with given vertex parity Let $G$ be a graph. Let $O$ be the number of edge induced subgraphs of $G$ having an odd number of vertices.


  Questions  
  
  
  How hard is to compute $O$?
  How hard is to compute the parity of $O$? 
  




Related questions:


Number of (vertex induced) subgraphs with given edge parity Answer: Tractable.
Number of (edge induced) 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, 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?
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.  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 this paper, 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.