# maximum weighted matching with weights being sets

Given a set $$S$$ and a bipartite graph $$G$$, each edge $$v\in E(G)$$ covers a subset $$S_v$$ of $$S$$. My problem is to find a matching maximizing the number of covered elements, i.e., denote $$V$$ the set of edges in the matching, we seeks to maximize $$|\bigcup_{v\in V} S_v|$$.

Your problem is NP-complete as we can translate instances of set-covering problems to your problem:

Let $$S$$ be a family of sets, its members be subsets of $$\{1,2,...,n\}$$. The set-covering problem is:

Does there exists $$m$$ members of $$S$$ whose union is $$\{1,2,...,n\}$$?

To translate the instance to your problem, construct a bipartite graph with vertices $$\{1,2,...,m\} \cup S$$ and edges the elements of $$\{1,2,...,m\}\times S$$. Assign the set $$s$$ to the edge $$(k,s)$$, where $$k$$ is a number and $$s$$ is a member of $$S$$. Thus any matching corresponds to $$m$$ members of $$S$$, and maximum number of covered elements can be achieved if and only if there exists $$m$$ members of $$S$$ with union $$\{1,2,...,n\}$$.

As the set-covering problem is NP-complete, your problem is also NP-complete.

• Thank you. It seems logical to me that the problem is NP-complete. Any clue on designing approximation algorithm? – lchen Jan 7 at 11:34
• Using linear programming may be possible, by combining the LP formulations of bipartite maximum weight matching and set covering. – LeechLattice Jan 7 at 11:42
• does edmonds-blossom or karp algorithm help here? – vidyarthi Jan 7 at 22:03
• Thank you. edmonds-blossom or karp algorithm cannot be directly applied here as the construction of augmenting path is by nature different. Just wonder whether a related formulation is tractable or not: now I am interested in deciding whether there exists a matching of $G$ that covers all the elements of $S$. – lchen Jan 8 at 2:35