25
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sajin Koroth Mar 22 '12 at 10:29
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Mar 22 '12 at 11:25
  • $\begingroup$ @TsuyoshiIto: Yes you are correct. It should have been "choose a $k$ such that, the naive approach takes $O(2^n)$ time". $\endgroup$ – Sajin Koroth Mar 22 '12 at 12:49
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Mar 22 '12 at 15:24
  • 4
    $\begingroup$ 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. $\endgroup$ – bbejot Mar 25 '12 at 4:21
6
$\begingroup$

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/

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.