Let $G$ be a graph. Let $O$ be the number of edge induced subgraphs of $G$ having an odd number of vertices.
- How hard is to compute $O$?
- How hard is to compute the parity of $O$?
- 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?