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.

Improve this question
$\endgroup$
9
  • $\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
    Commented Mar 22, 2012 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
    Commented Mar 22, 2012 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
    Commented Mar 22, 2012 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
    Commented Mar 22, 2012 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
    Commented Mar 25, 2012 at 4:21

2 Answers 2

Reset to default
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/

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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