Counting length-k increasing subsequences in a permutation

Question

(Originally posted on Math.SE.)

Let $f$ be a permutation on $n$ letters. I want to count the number of $k$-long increasing subsequences quickly.

One approach is to first use divide and conquer to split the problem into finding increasing subsequences in pairs of numbers. The resulting 'tree' then has height $\log n$. I'm wondering how the subproblems could be combined in an efficient way. I thought about prefix sums and using mergesort, but I can't see how to effectively implement them.

One idea to save time when combining two subproblems is to compare elements at the end of the increasing subsequences in the first subproblem with values in the second subproblem.

My goal is to get to $O(k n \log n)$ time but this doesn't do it.

Answer 1

According to Kim, finding one such sequence is equivalent to finding a maximum independent set in a permutation graph and can be done in $O(n\log n)$ time. The running time you're looking for suggests you already knew about that, but if not, looking at citing papers might help.

Update: actually, the complement of a permutation graph is also a permutation graph, and the complement of an independent set is a clique, so unless I'm missing something, maximising the number of increasing sequences of length $k$ in your permutation should be equivalent to partitioning a permutation graph into as many $K_k$'s as possible. Surely this has been studied, at least for triangles...

Answer 2

The time complexity we need is $O(kn\log n)$. That implies if we have an algorithm, that from the number of $k-1$-long increasing subsequences it counts the number of $k$-long subsequences in $O(n\log n)$ time, we are done. We use prefix sums for storing the actual number of $(k-1)$-long subsequences up to the $l$th element, where the individual entries are the number of (k-1)-long subsequences which ends at $l$th position.

Initialization: The number of 1-long increasing subsequences is 1 for all individual entries.

We read the individual entries of this data structure in $O(2\log n)$ time in the following way: read the prefix up to $l$ and then up to $l-1$ then extract it. At the beginning of making the $k$-length subsequences we make two empty (all-zero) prefix sums. Then we read the number of $k-1$-long subsequences up to $\pi(1)$. We update one of the table's (denote it $k$-table) $\pi(1)$th entry with the prefix the other (denote it $k-1$-table). Then we update the $k-1$-table's $\pi(1)$th entry with the number of $k-1$-long subsequences ending at $\pi(1)$. We do it also with $\pi(2)$, $\pi(3)$, \dots, $\pi(n)$.

We used only constant number of readings and updates for each $\pi(i)$. So the time complexity is $O(n\log n)$.

When updating the $l$th individual entry of the $k$-table we do the following. We count the number of $k-1$-long subsequences that ends before $\pi(i)$. So that at the ending position of the subsequence the permutation element is smaller than $i$. That is why we need the auxiliary $k-1$-table.