# Number of subgraphs with a given number of nodes

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
• 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. Aug 29 '12 at 21:38
• You define an induced subgraph but your question didn't use this defition. Did you mean to use it? Aug 29 '12 at 22:10
• 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. Aug 30 '12 at 1:51
• @TsuyoshiIto: Yes, I'm talking about edge-induced subgraphs. Aug 30 '12 at 6:01
• @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$. Aug 30 '12 at 6:11

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