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