5
$\begingroup$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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