computer science - Counting subgraphs of bipartite graphs

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