Is this subsequence problem NP-hard?

Question

Here is yet another "is X NP-hard?" question.

The input of the problem is the following:

• A sequence of $n$ non-negative real numbers $\alpha_1, \ldots, \alpha_n$. Here $n$ is a positive natural number. If it makes any difference, I would also be fine with the assumptions that the $\alpha$'s are integers instead of reals.
• A non-negative real number $\beta$. (Again, this number could be integer if it makes any difference.)
• An integer number $d$ such that $1 \leq d < n$.
• An integer number $t$ such that $1 \leq t \leq n$.

The problem asks whether there is a subsequence of $(\alpha _1, \ldots, \alpha_n)$ of length at most $t$ such that:

1. The sum of the elements in the subsequence is at least $\beta$. I.e., if the subsequence is $\alpha_{i_1}, \ldots, \alpha_{i_t}$, then $\sum_{j=1}^t \alpha_{i_j} \geq \beta$.
2. There is no gap larger than $d$ in the subsequence. For example, if a number $\alpha_i$ is in the subsequence, it cannot happen than none of the numbers $\alpha_{i-d}, \ldots, \alpha_{i-1}, \alpha_{i+1}, \ldots, \alpha_{i+d}$ are in the sub-sequence. In other words, if two numbers $\alpha_i$, $\alpha_j$ are in the subsequence and $j > i + d$, then there must be at least another number in the subsequence among $\alpha_{i+1}, \ldots, \alpha_{j-1}$.

I spent quite some time on it, but I could not come up with any reduction from NP-complete problems I am familiar with. At the same time, I do not have a polynomial-time algorithm for it. The best I have is a pseudopolinomial-time dynamic programming algorithm which runs in $O(n \beta)$ (when $\beta$ is integer).

Answer 1

I think this can be solved in PTIME by a rather standard dynamic programming approach.

Define a table $T$ storing, for each prefix length $i$, for each distance $j$, for each sequence length $l$, the maximum weight of a subsequence of the prefix of length $i$ of the input sequence such that the latest selected element is at distance $j$ from the end of the prefix (i.e., letting $x$ the latest selected element, $i-x = j$), and the number of selected elements is $l$. Initialize all cells to $-\infty$.

The table is of polynomial size as it has at most $n^3$ cells.

Now, we can compute the values for $i+1$ from the values for $i$, i.e., for each $i,j,l$, if $j$ is sufficiently small to satisfy condition 2, update $T[i+1,0,l+1]$ to take the max of its current value and of the $i$-th value plus $T[i,j,l]$ (intuitively, we add the leftmost element to the sequence), and update $T[i+1,j+1,l]$ to take the max of its current value and of $T[i,j,l]$ (intuitively, we do not add the leftmost element to the sequence).

This should satisfy the inductive invariant given in the first paragraph, and your desired answer would be the max of $T[n,j,l]$ over all suitable values of $j$ and all $l \leq t$. This algorithm runs in polynomial time.

(I hope this is clear and I didn't misunderstand your problem.)

Answer 2

Following the suggestion by Manuel Lafond, you can build a table with $O(n^2)$ entries. Entry $M(i,k)$ contains the maximum sum of a valid subsequence of elements $\{\alpha_1, \ldots, \alpha_i\}$ of length $k$ and such that the last element of the subsequence is $\alpha_i$.

Note that, trivially, $M(i, 1) = \alpha_i$ for all $i \in \{1,\ldots,n\}$.

Also note that if a subsequence of length $k$ ends at $\alpha_i$, then there must be at least another element among $\{\alpha_{i-d}, \ldots, \alpha_{i-1}\}$ in position $k-1$ in the subsequence. Otherwise, the "no gap" condition would be violated. From this last observation, you can derive the Dynamic Programming recursion: $$M(i, k) = \max_{i'=[i-d], \ldots, i-1} \{ M(i', k-1) \} + \alpha_i$$ where $[i-d] = \max \{ 1, i-d \}$.

Finally, there is a subsequence of length at most $t$ with a sum of at least $\beta$ if: $$\min \biggl\{ k=1,\ldots,n \; \bigl|\bigr. \; \exists i \in \{k,\ldots,n\} \text{ s.t. } M(i,k) \geq \beta \biggr\} \leq t$$

Interestingly, I stumbled across the same problem very recently, in the context of a special case of the min-Knapsack Problem (in which the $\alpha_i$ are weights, $\beta$ is the capacity and profits are all unitary).