Computational complexity of counting induced subgraphs which admit perfect matchings

Question

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.

• Sajin Koroth: 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.
• Tsuyoshi Ito: @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.
• Sajin Koroth: @TsuyoshiIto: Yes you are correct. It should have been "choose a $k$ such that, the naive approach takes $O(2^n)$ time".
• Tsuyoshi Ito: @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.
• bbejot: 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.

Answer 1

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/

• The Amplitwist: The link to springerlink.com is broken, but the article can be found at doi:10.1007/BF01294456.

Answer 2

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.