<p>The problem admits an FPTRAS. This is a randomized algorithm $\mathbb{A}$ that gets a graph $G$, a parameter $k\in \mathbb{N}$, and rational numbers $\epsilon &gt;0$ and $\delta \in (0,1)$ as inputs. If $z$ is the number of $k$-vertex sets you are looking for, then $\mathbb{A}$ outputs a number $z'$ such that
\begin{equation}
\mathbb{P}(z' \in [(1-\epsilon)z,(1+\epsilon)z]) \geq 1-\delta, 
\end{equation}
and it does so in time $f(k)\cdot g(n,\epsilon^{-1},\log \delta^{-1})$, where $f$ is some computable function and $g$ is some polynomial.</p>

<p>This follows from Thm. 3.1 in <a href="http://arxiv.org/abs/1308.1575">(Jerrum, Meeks 13)</a>: Given a property $\Phi$ of graphs, there is an FPTRAS, with the same input as above, that approximates the size of the set
\begin{equation}
\{S \subseteq V(G) \mid |S| =k \wedge \Phi(G[S])\},
\end{equation}
provided that $\Phi$ is computable, monotone, and all of its edge-minimal graphs have bounded treewidth. All three conditions hold if $\Phi$ is the graph property of admitting a perfect matching.</p>

CC BY-SA 3.0
2013-11-16T03:28:17.527Z
2013-11-16T03:28:17.527Z
Radu Curticapean
<p>The problem is #P-complete. It follows from the last paragraph of page 2 of the following paper:</p>

<p>C. J. Colbourn, J. S. Provan, and D. Vertigan, The complexity of computing the Tutte
polynomial on transversal matroids, Combinatorica 15 (1995), no. 1, 1–10.</p>

<p><a href="http://www.springerlink.com/content/wk55t6873054232q/" rel="noreferrer">http://www.springerlink.com/content/wk55t6873054232q/</a></p>

CC BY-SA 3.0
2012-04-19T19:24:10.997Z
2012-04-19T19:24:10.997Z
h.a
<p>Given an undirected and unweighted graph $G=(V,E)$ and an even integer $k$, what is the computational complexity of counting sets of vertices $S\subseteq V$ such that $|S|=k$ and the subgraph of $G$ restricted to the vertex set $S$ admits a perfect matching? Is the complexity #P-complete? Is there a reference for this problem?</p>

<p>Note that the problem is of course easy for a constant $k$ because then all the subgraphs of size $k$ can be enumerated in time ${|V| \choose k}$. Also note that the problem is different from counting the number of perfect matchings. The reason is that a set of vertices which admits a perfect matching may have multiple number of perfect matchings.</p>

<p>Another way to state the problem is as follows. 
A matching is called a $k$-matching if it matches $k$ vertices.
Two matchings $M$ and $M&#39;$ are ``vertex-set-non-invariant'' if the sets of vertices matched by $M$ and $M&#39;$ are not identical. We want to count the total number of vertex-set-non-invariant $k$-matchings.</p>

CC BY-SA 3.0
2012-03-22T10:29:02.953Z
When $k=\log n$, the number of such subsets is $\binom{|V|}{\log n}\leq n^{\log n}$, and checking if the graph induced by the subset has a perfect matching using Tutte's characterization takes $O(2^{\log n})=O(n)$ time, hence it is unlikely for it be even NP-complete unless exponential time hypothesis is wrong. Hence the interesting case is when $k=\theta(\frac{n}{\log n})$, in which case the naive approach takes $2^{O(n)}$ time, if you are looking for #P completeness.
Sajin Koroth
CC BY-SA 3.0
2012-03-22T11:25:22.200Z
@Sajin Koroth: I do not follow the last sentence in your comment.  For example, if k=√n, the naive approach takes $2^{n^{\Omega(1)}}$ time, and I do not think that this gives any evidence against it being #P-complete.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-22T12:49:06.650Z
@TsuyoshiIto: Yes you are correct. It should have been "choose a $k$ such that, the naive approach takes $O(2^n)$ time".
Sajin Koroth
CC BY-SA 3.0
2012-03-22T15:24:35.693Z
@Sajin Koroth: Why should one choose a value of k such that the naive approach takes $O(2^n)$ time?  Doing so does not probably hurt, but I do not see why one should do that.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-22T15:33:28.263Z
@TsuyoshiIto, if the naive approach itself is sub-exponential and it is also NP complete then you will disprove the exponential time hypothesis, which is unlikely. So it will be better (I am not saying that this is the best approach) if you look for a $k$ which makes sure that at least the naive approach takes exponential time if one is trying to prove the hardness of the problem.
Sajin Koroth
CC BY-SA 3.0
2012-03-22T16:18:52.990Z
@Sajin Koroth: You are confusing the two definitions of the term “sub-exponential”: $2^{n^{o(1)}}$ (the usual definition in complexity) and $2^{o(n)}$ (the weaker definition).  It is not surprising if some NP-hard problem can be solved in time $2^{o(n)}$; in fact it is easy to construct such an NP-complete problem.  Even if the current problem is NP-hard with k=√n, it has nothing to do with the exponential time hypothesis.  (more)
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-22T16:25:10.423Z
@Sajin Koroth: On the other hand, if some NP-hard problem can be solved in time $2^{n^{o(1)}}$, then the whole NP can be solved in such time, which is a big surprise; this is much stronger than the mere failure of the exponential time hypothesis.  However, for k=√n, the naive algorithm you mentioned still takes exponential time ($2^{n^{O(1)}}$ time; note the difference between small-o and big-O).
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-22T16:41:41.753Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2869/discussion-between-sajin-koroth-and-tsuyoshi-ito)
Sajin Koroth
CC BY-SA 3.0
2012-03-25T04:21:31.280Z
It seems that most problems of the sort "how man induced subgraphs of size k have property X?" are hard. Even the property "has an edge" is hard  ("Has an edge" solves "does not have an edge" which is "is a complete graph" in the duel... solves MAX CLIQUE). This really makes it feel that "has a perfect matching" will also be hard, but finding a proof is dificult right now.
bbejot
<cc.complexity-theory><co.combinatorics><counting-complexity>
Computational complexity of counting induced subgraphs which admit perfect matchings
h.a
# Computational complexity of counting induced subgraphs which admit perfect matchings

(Asked by: username_0 on 2012-03-21)

Given an undirected and unweighted graph $G=(V,E)$ and an even integer $k$, what is the computational complexity of counting sets of vertices $S\subseteq V$ such that $|S|=k$ and the subgraph of $G$ restricted to the vertex set $S$ admits a perfect matching? Is the complexity #P-complete? Is there a reference for this problem?

Note that the problem is of course easy for a constant $k$ because then all the subgraphs of size $k$ can be enumerated in time ${|V| \choose k}$. Also note that the problem is different from counting the number of perfect matchings. The reason is that a set of vertices which admits a perfect matching may have multiple number of perfect matchings.

Another way to state the problem is as follows.
A matching is called a $k$-matching if it matches $k$ vertices.
Two matchings $M$ and $M'$ are ``vertex-set-non-invariant'' if the sets of vertices matched by $M$ and $M'$ are not identical. We want to count the total number of vertex-set-non-invariant $k$-matchings.

**Tags:** cc.complexity-theory, co.combinatorics, counting-complexity
> **Comments:**
> **username_1**: When $k=\log n$, the number of such subsets is $\binom{|V|}{\log n}\leq n^{\log n}$, and checking if the graph induced by the subset has a perfect matching using Tutte's characterization takes $O(2^{\log n})=O(n)$ time, hence it is unlikely for it be even NP-complete unless exponential time hypothesis is wrong. Hence the interesting case is when $k=\theta(\frac{n}{\log n})$, in which case the naive approach takes $2^{O(n)}$ time, if you are looking for #P completeness.  
> **username_2**: @Sajin Koroth: I do not follow the last sentence in your comment.  For example, if k=√n, the naive approach takes $2^{n^{\Omega(1)}}$ time, and I do not think that this gives any evidence against it being #P-complete.  
> **username_1**: @TsuyoshiIto: Yes you are correct. It should have been "choose a $k$ such that, the naive approach takes $O(2^n)$ time".  
> **username_2**: @Sajin Koroth: Why should one choose a value of k such that the naive approach takes $O(2^n)$ time?  Doing so does not probably hurt, but I do not see why one should do that.  
> **username_1**: @TsuyoshiIto, if the naive approach itself is sub-exponential and it is also NP complete then you will disprove the exponential time hypothesis, which is unlikely. So it will be better (I am not saying that this is the best approach) if you look for a $k$ which makes sure that at least the naive approach takes exponential time if one is trying to prove the hardness of the problem.  
> **username_2**: @Sajin Koroth: You are confusing the two definitions of the term “sub-exponential”: $2^{n^{o(1)}}$ (the usual definition in complexity) and $2^{o(n)}$ (the weaker definition).  It is not surprising if some NP-hard problem can be solved in time $2^{o(n)}$; in fact it is easy to construct such an NP-complete problem.  Even if the current problem is NP-hard with k=√n, it has nothing to do with the exponential time hypothesis.  (more)  
> **username_2**: @Sajin Koroth: On the other hand, if some NP-hard problem can be solved in time $2^{n^{o(1)}}$, then the whole NP can be solved in such time, which is a big surprise; this is much stronger than the mere failure of the exponential time hypothesis.  However, for k=√n, the naive algorithm you mentioned still takes exponential time ($2^{n^{O(1)}}$ time; note the difference between small-o and big-O).  
> **username_1**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2869/discussion-between-sajin-koroth-and-tsuyoshi-ito)  
> **username_3**: It seems that most problems of the sort "how man induced subgraphs of size k have property X?" are hard. Even the property "has an edge" is hard  ("Has an edge" solves "does not have an edge" which is "is a complete graph" in the duel... solves MAX CLIQUE). This really makes it feel that "has a perfect matching" will also be hard, but finding a proof is dificult right now.  

---

## 2 answers

### Answer by username_4 on 2013-11-16. Score: 6

The problem admits an FPTRAS. This is a randomized algorithm $\mathbb{A}$ that gets a graph $G$, a parameter $k\in \mathbb{N}$, and rational numbers $\epsilon >0$ and $\delta \in (0,1)$ as inputs. If $z$ is the number of $k$-vertex sets you are looking for, then $\mathbb{A}$ outputs a number $z'$ such that
\begin{equation}
\mathbb{P}(z' \in [(1-\epsilon)z,(1+\epsilon)z]) \geq 1-\delta,
\end{equation}
and it does so in time $f(k)\cdot g(n,\epsilon^{-1},\log \delta^{-1})$, where $f$ is some computable function and $g$ is some polynomial.

This follows from Thm. 3.1 in [(Jerrum, Meeks 13)](http://arxiv.org/abs/1308.1575): Given a property $\Phi$ of graphs, there is an FPTRAS, with the same input as above, that approximates the size of the set
\begin{equation}
\{S \subseteq V(G) \mid |S| =k \wedge \Phi(G[S])\},
\end{equation}
provided that $\Phi$ is computable, monotone, and all of its edge-minimal graphs have bounded treewidth. All three conditions hold if $\Phi$ is the graph property of admitting a perfect matching.


---

### Answer by username_0 on 2012-04-19. Score: 6

The problem is #P-complete. It follows from the last paragraph of page 2 of the following paper:

C. J. Colbourn, J. S. Provan, and D. Vertigan, The complexity of computing the Tutte
polynomial on transversal matroids, Combinatorica 15 (1995), no. 1, 1–10.

<http://www.springerlink.com/content/wk55t6873054232q/>


---

