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.

  • 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

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

  • $\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

