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

• Tsuyoshi Ito: Note that your problem is a generalization of the problem of counting the independent sets of given size in a given graph, which is at least as hard as deciding whether a given graph has an independent set of given size. This at least gives the negative answer to your question 1 unless P=NP.
• Tyson Williams: You define an induced subgraph but your question didn't use this defition. Did you mean to use it?
• Tsuyoshi Ito: Ah, you were talking about edge-induced subgraphs, whereas I incorrectly thought that you were talking about vertex-induced subgraphs. My previous comment is not true as is written. Please replace "independent set" in my previous comment with "clique," and the same conclusion holds for question 1.
• Giorgio Camerani: @TsuyoshiIto: Yes, I'm talking about edge-induced subgraphs.
• Giorgio Camerani: @TysonWilliams: The question implicitly uses the definition of edge-induced subgraph. $k_3$ is the number of edge-induced subgraphs of $G$ having $k_1$ edges and $k_2$ nodes. The number of edge-induced subgraphs of $G$ having $k_1$ edges is ${|E_G| \choose k_1},ドル one for each subset $E_H \subseteq E_G$ such that $|E_H| = k_1$.

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