Counting subgraphs of bipartite graphs

Question

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).]

Answer 1

I don't know the answer, just some thoughts.

Suppose you have $n$ vertices of the first type and $l$ of the second. Of course, you know the answer if there is no restriction on the number of edges (you want it to be odd). Therefore equivalently I can calculate cases, when it is odd with coefficient (-1) and cases, when it is even with coefficient 1 (I denote this amount by $N$). Let $y_1,\dots,y_n,z_1,\dots,z_l$ be elements of $\mathbb{Z}\_2=\mathbb{Z}/(2\mathbb{Z})$, corresponding to the vertices of the graph. Edges are given by $n\times l$ matrix $A$. Then $N$ is the coefficient of $h^m$ in $S(h,h)$, where $S$ is defined by $$S(h,g)=\sum_{y\in\mathbb{Z}\_2^n,\;z\in\mathbb{Z}\_2^l} h^{|y|} g^{|z|} (-1)^{\sum_{i,j}y_i A_{ij} z_j}.\tag{1}$$ Here $|y|$ is amount of components in $y\in \mathbb{Z}\_2^n$ which are equal to $1$. One can get rid of the sum over $y\in\mathbb{Z}\_2^n$ in the following way: $$S(h,g)=\sum_{z\in\mathbb{Z}\_2^l} g^{|z|}\prod_{i=1}^{n} (1+h(-1)^{\sum_j A_{ij} z_j}).\tag{2}$$ This for example solves the problem in two cases:
1. we fix the number of vertices only in one part of a bipartite graph and the map $\mathbb{Z}_2^l\to\mathbb{Z}_2^n\colon z\mapsto x$ with $x_i=\sum_j A_{ij} z_j$ is surjective (in this case we can omit $g^{|z|}$ in $(2)$, make described change of coordinates and apply again the trick we used to get (2) from (1));
2. amount of vertices in one part of a bipartite graph is small enough (in this case the sum (2) has small enough number of terms and each of them can be calculated in a polynomial time);

Answer 2

Unfortunately, I don't have an answer. The following observation lets me think that a clever brute force solution is near at hand, and may even find its way to an enumeration.

If m were n-1, the problem would be easy: determine the parity of the number of edges of the graph G, and determine the parity of the degree of each edge. Then the number of subgraphs on n-1 vertices with an odd number of edges is the same as the number of vertices whose degree has parity opposite that of parity of G.

Now if I were doing a brute force algorithm, and m satisfied 2*m > n, then I might use the above observation to look at the induced subgraphs on (m+1) vertices and then do the calculations over a covering set of the (m+1) subgraphs. Or there might be a 2-step version where I could use pairs of vertices in an (m+2) subgraph. It is tempting to think there is also an (n-m)-step version using generating functions or Polya enumeration, but I don't know enough to tell you about those.

When I am able to comment, then I might turn this musing from an answer into a comment.

Gerhard "Ask Me About System Design" Paseman, 2010.02.04