# Computational complexity of counting induced subgraphs which admit perfect matchings

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.

• 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
• 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 4:21

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.

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 $$\mathbb{P}(z' \in [(1-\epsilon)z,(1+\epsilon)z]) \geq 1-\delta,$$ 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 $$\{S \subseteq V(G) \mid |S| =k \wedge \Phi(G[S])\},$$ 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.