4
$\begingroup$

Consider the following problem: Given is a multiset of positive integers, $S$, and an integer $k$. Count submulisets of $S$ of size $k$, $\{s_1,\dotsc,s_k\} \subseteq S$, such that when the $s_i$ are ordered increasingly, $s_i \geq i$.

Can this problem be done in polynomial time (polynomial in size of $S$)?

Background: This is a very special case of counting independent subsets of a graph, (which is hard), but I suspect this special case might be solvable via some clever dynamic programming.

$\endgroup$
  • 1
    $\begingroup$ Just to clarify one more time. If $S = \{2,2\}$ and $k = 1$, should the answer be $1$ or $2$? $\endgroup$ – Mikhail Rudoy Mar 1 '17 at 0:25
3
$\begingroup$

If $S = \{2,2\}$ and $k=1$, the answer is $2$, the following dynamic program works.

Let $S = \{a_1,a_2,...,a_{|S|}\}$ where $a_i \leq a_{i+1}$. Consider the function $DP(i,n)$ as the number of satisfying subsets ending with element $i$ of length $n$. A satisfying set is a set $T = \{s_1,s_2,...,s_{k'}\}$ with the property $i \leq s_i \leq s_{i+1}$.

Hence, $DP(i,n) = 0$ if $a_i \leq n$, $1$ if $n = 1$. Otherwise, $DP(i,n) = \sum_{j=1}^{i-1} DP(j,n-1)$. The answer will then be $\sum_{j=1}^{|S|} DP(j,k)$.

If indeed for the case $S = \{2,2\}$ and $k=1$, the answer is $1$. A small modification to the above recurrence is possible. Consider a representation of a multiset $S$ in the form $\{(a_1,b_1),(a_2,b_2),...,(a_n, b_n)\}$ where $a_i < a_{i+1}$ and $b_i$ is the number of copies of $a_i$ in $S$.

$\endgroup$
  • $\begingroup$ That is very nice! Indeed, your example should have two solutions (take the first, or the second 2). $\endgroup$ – Per Alexandersson Mar 1 '17 at 3:31

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.