2
$\begingroup$

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|$.

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.