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.


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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.