1
$\begingroup$

Consider this variant of multiset covering problem.

Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ and $s_k \neq \emptyset$ for all $k$.

The problem is, given an non-empty multiset $M$ containing elements from $U$, we are allowed to pick at most one element from each set in $S$ to form a new multiset $P$. We need $P$ to cover $M$ as many times as possible. For $P$ to cover $M$ $n$ times means for each element in $M$, there are at least $n$ copies in $P$.

For example, if $S = \{\{1, 2, 3\}, \{2, 3\}, \{2\}, \{2\}, \{1\}, \{1\}, \{1, 3\}\}$ and $M = \{1, 1, 2\}$, we should be able to form $P = \{1, 2, 2, 1, 1, 1\}$ by picking 1 element from the 1st, 2nd, 3rd, 5th, 6th and 7th sets respectively. This will cover $M$ 2 times. (To cover $M$ 3 times will require six $1$s and three $2$s, which is impossible from just 7 sets)

Is the above problem NP-Hard?

$\endgroup$

1 Answer 1

1
$\begingroup$

This is a matching problem and can therefore be solved efficiently.

Make a bipartite graph where one side is $S$, and the other side is $B$, made up of $n$ copies of $M$. If you enumerate the elements of $M$, $m_1,\ldots,m_k$, then $b_{i,j}\in B = m_j$ for all $i\in [n]$. Then draw an edge from $s_\ell$ to $b_{i,j}$ iff $m_j\in s_\ell$ for all $i,j,\ell$. Now it's easy to see that you can cover $M$ $n$ times iff there is a matching in the graph with $|B|$ edges. Trying with different sizes of $n$, you can find the greatest one.

There is probably a more efficient way to find a matching that saturates one side $n$ times (such that you only need one copy of $M$), but this at least shows that the problem is not NP-hard (unless P=NP, of course).

$\endgroup$

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.