# Is this subsequence problem NP-hard?

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

• Have you looked at longest increasing subsequence and similar problems? The dynamic programming ideas from there might be adaptable. For instance, if you define $M(i, k)$ as the maximum sum achievable in $\alpha_1, \ldots \alpha_i$ with the restriction that $\alpha_i$ is the $k$-th number in the subsequence, then maybe you can calculate $M(i, k)$ in terms of $M(i - 1, k - 1), \ldots, M(i - d, k - 1)$. Dec 4, 2022 at 16:33
• Your two versions of condition 2 are not equivalent. Which one did you intend?
– D.W.
Dec 5, 2022 at 3:43
• Also, the first definition used in condition 2 seems to count a subsequence like $\alpha_1, \alpha_2, \alpha_{n-1}, \alpha_{n}$ as having no gaps > 1 since for each $\alpha$ there is another within distance 1.
– mhum
Dec 6, 2022 at 22:52

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

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