Number of subgraphs with a given number of nodes

Question

Let $G = ( V_G, E_G )$ be a graph. Let $E_H \subseteq E_G$.

The subgraph of $G$ edge-induced by $E_H$ is $H = ( V_H, E_H)$, where

$V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$

Let $k_1 \leq |E_G|$ and $k_2 \leq |V_G|$ be given in input.

I would like to determine the number $k_3$ of edge-induced subgraphs of $G$ having $k_1$ edges and $k_2$ nodes. Clearly, I don't want to enumerate all the (exponentially many) subgraphs of $G$ having $k_1$ edges.

Questions:

1. Is it possible to determine $k_3$ in time polynomial in $|E_G|$?
2. What if $G$ is 3-regular?
3. What if $G$ is 3-regular planar?
4. What if $G$ is 3-regular planar bipartite?
5. Which is the best known algorithm to compute $k_3$? $\longleftarrow$ Added on 30/08/2012

Answer 1

Let $f(G, k_1, k_2)$ be the counting problem that you have defined. Then $$g(G) = \sum_{k_1 = 0}^{|V_G| / 2} f(G, k_1, 2 k_1)$$ counts the number of matchings in $G$, which only uses a linear number of oracle calls to your problem.

Since counting matchings in 3-regular planar graphs is #P-hard (see ref below), your questions (1), (2), and (3) all give a #P-hard problem. Your last question (4) probably gives a #P-hard problem as well because counting matchings in 3-regular biparitie planar graphs is probably #P-hard, but I don't know if anyone has proved this. The closest that I know of is that

1. counting matchings in 2,3-regular biparitie planar graphs is #P-hard and
2. counting matchings in biparitie planar graphs of max degree 6 is #P-hard.

The reference that I promised above is Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP by Jin-Yi Cai, Pinyan Lu, Mingji Xia. Theorem 6.1 proves that counting matchings in 3-regular planar graphs is #P-hard in the special case that $[y_0, y_1, y_2] = [1,0,1]$ and $[x_0, x_1, x_2, x_3] = [1,1,0,0]$.