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$

1 Answer 1

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.

$\endgroup$
4
  • $\begingroup$ Thank you. It seems logical to me that the problem is NP-complete. Any clue on designing approximation algorithm? $\endgroup$
    – lchen
    Jan 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$
    – vidyarthi
    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$
    – lchen
    Jan 8, 2020 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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