# Perfect Matching with set-over-like" constraints?

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

• 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.
Jul 27, 2015 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.
• 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$. Jul 28, 2015 at 13:48