2
$\begingroup$

I have a collection of subsets $\{S_1,\ldots,S_m\}$ where each $S_i\subset \{1,\ldots,n\}$. I would like to cover the maximum number of elements from $\{1,\ldots,n\}$ by choosing a single element from each $S_i$. What is the optimal way to do this?

For example, say I have $S_1=\{1\}$ and $S_2=\{2,3\}$ and $S_3=\{3\}$ and $n=3$. If my algorithm picks randomly (or the maximum number say) a number from each $S_i$, then I could obtain a solution that covers only $\{1,3\}$ but there is a solution that covers all elements.

$\endgroup$
2
$\begingroup$

This problem is the same as the problem of finding the maximum matching in bipartite graphs, which can be solved by the Ford-Fulkerson algorithm in $O((n+m)s)$ time or the Hopcroft-Karp algorithm in $O(\sqrt{n+m}s)$ time, where $s$ is the number of elements in all $S_i$ combined.


Given a collection of subsets $\{S_1,\ldots,S_m\}$ where each $S_i\subset \{1,\ldots,n\}$, let $G$ be the graph with nodes $\{1, 2, \cdots, n, S_1,S_2,\cdots,S_m\}$. Whenever $j\in S_i$, there is an edge $e_{j,S_i}$ in $G$ that connects node $j$ and node $S_i$. $G$ is a bipartite graph with vertex sets $X=\{1, 2, \cdots, n\}$ and $Y=\{S_1,S_2,\cdots,S_m\}$

Suppose we have selected $k_i$ from $S_i$ for all $i$. Having removed duplicate numbers among ${k_1}, {k_2}, \cdots, {k_m}$, we can assume $\{k_i\mid i\in I\}$ for some $I\subseteq \{1,2,\cdots,m\}$ is the set of distinct numbers among them. Then $\{e_{k_i, S_i}\mid i\in I\}$ is a matching in $G$.

Conversely, if we have a matching $\{e_{k_i, S_i}\mid i\in I\}$ in $G$ for some $I\subseteq \{1,2,\cdots,m\}$, we can select $k_i$ from $S_i$ when $i\in I$ while selecting any element from $S_i$ when $i\not\in I$.

The above two conversions show that the problem in the question, finding the maximal number of selected elements is the same as the problem of find the cardinality of the maximum matching in a bipartite graph. Note that the conversion takes linear time or polynomial time depending on which parameters are used.


Here is a variation for which I do not know if there exists a polynomial algorithm.

Problem. What if we select two elements from each set, assuming each set has at least two elements?

$\endgroup$
-1
$\begingroup$

This is the hitting set problem, you can find greedy algorithm for solving it.

$\endgroup$
  • 2
    $\begingroup$ We discourage one-line answers. Can you justify your answer? Can you justify why you think it is the hitting set problem? I don't think it is; in the hitting-set problem, we're trying to use the minimum number of elements of $\{1,\dots,n\}$, not the maximum number, and there's no requirement to avoid covering two sets with the same element. $\endgroup$ – D.W. Jan 10 at 6:21

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.