Problem Description:

Let k and n be some natural numbers. We are given a complete bipartite graph G where each side of G has n vertices. G is edge-labeled with labels being subsets of {1,...,k}. We are looking for a perfect matching G' such that the union of sets labeling edges of G' equals {1,...,k}.

The problem is clearly NP-hard in k, but is it also NP-hard in n? I.e. can one achieve an algorithm that is polynomial in n while possibly being exponential in k (maybe via adaptation of the Dynamic Programming algorithm for set cover..)?

Many thanks, Amir

  • 1
    $\begingroup$ What have you tried? Have you tried working out what happens for small values of $k$, and then seeing if you can generalize? For $k=1$ it's clearly in P. Have you looked at the special case $k=2$ to see what happens there? It seems that case is also in P. $\endgroup$ – D.W. Jul 27 '15 at 22:35

The problem can be solved in $O(n^k \, \text{poly}(n))$ time, so it's not "NP-hard in $n$" unless P=NP.

Here's one simple algorithm. Enumerate all subsets $E'$ of $E$ such that $|E'|\le k$. Check whether the union of labels of $E'$ is equal to $\{1,2,\dots,k\}$; if not, move on to the next candidate for $E'$. Then, check whether there's a perfect matching of $G$ that includes all edges of $E'$. This can be done as follows: check that no pair of edges in $E'$ meets in a common vertex; let $V^*$ be the set of vertices that don't touch any edge of $E'$, and $E^*$ the set of edges both of whose endpoints are in $V^*$; then check whether $G^*=(V^*,E^*)$ has a perfect matching. If such a perfect matching exists, you have found a valid solution to your original problem. There are $O(n^k)$ possible subsets $E'$, so the entire procedure runs in $O(n^k \, \text{poly}(n))$ time. Correctness follows because if there is a set of edges whose labels have union equal to $\{1,2,\dots,k\}$, then there is a set of size $\le k$ with this property.

  • 1
    $\begingroup$ Wouldn't you actually want to enumerate all $E'$ with $|E'|\le k$? For $k>n$ in particular you run into trouble if you require $|E'| = k$. $\endgroup$ – Klaus Draeger Jul 28 '15 at 13:48
  • $\begingroup$ @KlausDraeger, yes, you are right. Thank you. $\endgroup$ – D.W. Jul 28 '15 at 16:29

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.