# Finding the longest sub-permutation with bounded inversion number

Given a permutation $\sigma\in S_n$ and a positive integer $k$, find the largest integer $0\le m\le n$ such that there exist a subset $I\subseteq [n], |I|=m$, satisfying that the restriction of $\sigma$ on $I$ has inversion number bounded by $k$. (Here the restriction of a permutation is defined in the very natural way that you can imagine.)

I wonder if the above problem was studied before? Any ideas/previous results on algorithm/approximation algorithm/hardness result are appreciated.

• When k=0 this is just finding a longest increasing subsequence which is easy. In general I'm less sure. – Artimis Fowl Oct 9 '17 at 23:28
• @Artimis Fowl Yes you are right! The case k=0 can be solved via dynamic programming. Actually this also gives a trivial k-additive approximation algorithm to the general problem, but I do not know of any better approximation. – Zihan Tan Oct 10 '17 at 3:33
• Actually this problem is equivalent to finding the sparsest t-subset in permutation graph. To the best of my knowledge, there is no known non-trivial approximation algorithm to it yet. – Zihan Tan Oct 11 '17 at 1:25