<p>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.</p>

<p>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</p>

<ol>
<li><a href="http://www.sciencedirect.com/science/article/pii/S0304397507004653">counting matchings in 2,3-regular biparitie planar graphs is #P-hard</a> and</li>
<li><a href="http://epubs.siam.org/doi/abs/10.1137/S0097539797321602">counting matchings in biparitie planar graphs of max degree 6 is #P-hard</a>.</li>
</ol>

<p>The reference that I promised above is <a href="http://arxiv.org/abs/1008.0683">Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP</a> 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]$.</p>

CC BY-SA 3.0
2012-08-30T14:16:03.307Z
2012-08-30T15:14:19.463Z
2012-08-30T15:14:19.463Z
Tyson Williams
<p>Let <span class="math-container">$G = ( V_G, E_G )$</span> be a graph. Let <span class="math-container">$E_H \subseteq E_G$</span>.</p>
<p>The subgraph of <span class="math-container">$G$</span> edge-induced by <span class="math-container">$E_H$</span> is <span class="math-container">$H = ( V_H, E_H)$</span>, where</p>
<p><span class="math-container">$V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$</span></p>
<p>Let <span class="math-container">$k_1 \leq |E_G|$</span> and <span class="math-container">$k_2 \leq |V_G|$</span> be given in input.</p>
<p>I would like to determine the number <span class="math-container">$k_3$</span> of edge-induced subgraphs of <span class="math-container">$G$</span> having <span class="math-container">$k_1$</span> edges and <span class="math-container">$k_2$</span> nodes. Clearly, I don't want to enumerate all the (exponentially many) subgraphs of <span class="math-container">$G$</span> having <span class="math-container">$k_1$</span> edges.</p>
<blockquote>
<p><strong>Questions:</strong></p>
<ol>
<li>Is it possible to determine <span class="math-container">$k_3$</span> in time polynomial in <span class="math-container">$|E_G|$</span>?</li>
<li>What if <span class="math-container">$G$</span> is 3-regular?</li>
<li>What if <span class="math-container">$G$</span> is 3-regular planar?</li>
<li>What if <span class="math-container">$G$</span> is 3-regular planar bipartite?</li>
<li>Which is the best known algorithm to compute <span class="math-container">$k_3$</span>? <span class="math-container">$\longleftarrow$</span> <strong>Added on 30/08/2012</strong></li>
</ol>
</blockquote>

CC BY-SA 3.0
2012-08-29T21:38:38.507Z
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
CC BY-SA 3.0
2012-08-29T22:10:20.400Z
You define an induced subgraph but your question didn't use this defition. Did you mean to use it?
Tyson Williams
CC BY-SA 3.0
2012-08-30T01:51:27.073Z
Ah, you were talking about [edge-induced subgraphs](http://mathworld.wolfram.com/Edge-InducedSubgraph.html), 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
CC BY-SA 3.0
2012-08-30T06:01:05.400Z
@TsuyoshiIto: Yes, I'm talking about edge-induced subgraphs.
Giorgio Camerani
CC BY-SA 3.0
2012-08-30T06:11:56.833Z
@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
CC BY-SA 3.0
2012-08-30T06:21:50.593Z
@TsuyoshiIto: If determining $k_3$ for a general graph $G$ is as hard as _counting_ cliques of a given size, then even P = NP wouldn't necessarily imply the possibility to determine $k_3$ in time polynomial in $|E_G|$. Am I missing something?
Giorgio Camerani
CC BY-SA 3.0
2012-08-30T12:17:07.840Z
No, you are not missing something.  I did not claim that if P=NP, there is a polynomial-time algorithm for your problem 1.  I am pretty sure that most of your problems are #P-complete, but I do not have a proof or a reference.
Tsuyoshi Ito
<ds.algorithms><graph-theory><graph-algorithms><counting-complexity>
Number of subgraphs with a given number of nodes
Giorgio Camerani
# Number of subgraphs with a given number of nodes

(Asked by: username_0 on 2012-08-29)

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**

**Tags:** ds.algorithms, graph-theory, graph-algorithms, counting-complexity
> **Comments:**
> **username_1**: 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.  
> **username_2**: You define an induced subgraph but your question didn't use this defition. Did you mean to use it?  
> **username_1**: Ah, you were talking about [edge-induced subgraphs](http://mathworld.wolfram.com/Edge-InducedSubgraph.html), 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.  
> **username_0**: @TsuyoshiIto: Yes, I'm talking about edge-induced subgraphs.  
> **username_0**: @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$.  
> **username_0**: @TsuyoshiIto: If determining $k_3$ for a general graph $G$ is as hard as _counting_ cliques of a given size, then even P = NP wouldn't necessarily imply the possibility to determine $k_3$ in time polynomial in $|E_G|$. Am I missing something?  
> **username_1**: No, you are not missing something.  I did not claim that if P=NP, there is a polynomial-time algorithm for your problem 1.  I am pretty sure that most of your problems are #P-complete, but I do not have a proof or a reference.  

---

## 1 answers

### Answer by username_2 on 2012-08-30. Score: 9 | Accepted 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

1. [counting matchings in 2,3-regular biparitie planar graphs is #P-hard](http://www.sciencedirect.com/science/article/pii/S0304397507004653) and
2. [counting matchings in biparitie planar graphs of max degree 6 is #P-hard](http://epubs.siam.org/doi/abs/10.1137/S0097539797321602).

The reference that I promised above is [Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP](http://arxiv.org/abs/1008.0683) 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]$.


---

