Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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$.
