I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed!

Given a bipartite graph $G$ of $n$ vertices, how many induced subgraphs of $m\leq n$ vertices are there for which the total number of edges of the subgraph is odd? Or, what is the computational complexity of making such a determination?

One way to rephrase this is to take a bit string $y\in\{0,1\}^n$ so that each bit $y_k$ specifies whether or not to keep the $k^{th}$ vertex. Then the question amounts to counting the number of satisfying instances of $\bigoplus_{\{k,l\}\in E}y_ky_l=1$, where $E$ denotes the edges of $G$, and constrained by the requirement that the Hamming weight of $y$ is $m$.

While I'm interested in a result for all bipartite graphs, I'm also interested in the special case of the square lattice. I've not been able to find exactly this problem anywhere, but there are a couple of cases which I think have been answered:

- If there is no restriction to the graph being bipartite, the problem is sharp-P complete [N. Creignou, H. Schnoor and I. Schnoor, Computer Science Logic 5213, 109 (2008), Springer Berlin.]
- If, instead, we don't have the restriction to the $m$-vertex subgraphs, and just ask how many induced subgraphs there are with an odd number of edges, there is an efficient algorithm for counting them [A. Ehrenfeucht and M. Karpinski, The Computational Complexity of (XOR, AND)-Counting Problems, Technical Report 90-033 (1990).]

2more comments