25

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.

h.a
  • 523
  • 3
  • 9
  • 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 Mar 22 '12 at 10:29
  • @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 Mar 22 '12 at 11:25
  • @TsuyoshiIto: Yes you are correct. It should have been "choose a $k$ such that, the naive approach takes $O(2^n)$ time". – Sajin Koroth Mar 22 '12 at 12:49
  • @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 Mar 22 '12 at 15:24
  • @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 Mar 22 '12 at 15:33
  • @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 Mar 22 '12 at 16:18
  • @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 Mar 22 '12 at 16:25
  • let us continue this discussion in chat – Sajin Koroth Mar 22 '12 at 16:41
  • 4
    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 Mar 25 '12 at 04:21

2 Answers2

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/

h.a
  • 523
  • 3
  • 9
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): 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.

Radu Curticapean
  • 817
  • 6
  • 12