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

<p>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.</p>

CC BY-SA 3.0
2015-07-28T13:48:16.910Z
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$.
Klaus Draeger
CC BY-SA 3.0
2015-07-28T16:29:02.077Z
@KlausDraeger, yes, you are right.  Thank you.
D.W.
CC BY-SA 3.0
2015-07-27T22:41:23.780Z
2015-07-28T16:28:51.363Z
2015-07-28T16:28:51.363Z
D.W.
<p>Problem Description:</p>

<p>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}.</p>

<p>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..)?</p>

<p>Many thanks,
Amir</p>

CC BY-SA 3.0
2015-07-27T22:35:30.683Z
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.
D.W.
<graph-theory><matching>
Perfect Matching with ``set-over-like" constraints?
Amir
# Perfect Matching with ``set-over-like" constraints?

(Asked by: username_0 on 2015-07-27)

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

**Tags:** graph-theory, matching
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2015-07-27. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_2**: 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$.  
> **username_1**: @KlausDraeger, yes, you are right.  Thank you.  

---

