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|$.
1 Answer
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.
-
$\begingroup$ Thank you. It seems logical to me that the problem is NP-complete. Any clue on designing approximation algorithm? $\endgroup$– lchenJan 7, 2020 at 11:34
-
$\begingroup$ Using linear programming may be possible, by combining the LP formulations of bipartite maximum weight matching and set covering. $\endgroup$ Jan 7, 2020 at 11:42
-
$\begingroup$ does edmonds-blossom or karp algorithm help here? $\endgroup$ Jan 7, 2020 at 22:03
-
$\begingroup$ 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$. $\endgroup$– lchenJan 8, 2020 at 2:35