# 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. – Tsuyoshi Ito 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? – Tyson Williams 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. – Tsuyoshi Ito Aug 30 '12 at 1:51
• @TsuyoshiIto: Yes, I'm talking about edge-induced subgraphs. – Giorgio Camerani 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$. – Giorgio Camerani Aug 30 '12 at 6:11

## 1 Answer

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

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