Number of edge induced subgraphs with given vertex parity

Question

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 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?

Answer 1

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} & \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, 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.