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

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

CC BY-SA 3.0
2017-10-09T23:28:08.907Z
When k=0 this is just finding a longest increasing subsequence which is easy. In general I'm less sure.
Artimis Fowl
CC BY-SA 3.0
2017-10-10T03:33:54.267Z
@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
CC BY-SA 3.0
2017-10-11T01:25:27.033Z
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
<co.combinatorics><permutations>
Finding the longest sub-permutation with bounded inversion number
Zihan Tan
# Finding the longest sub-permutation with bounded inversion number

(Asked by: username_0 on 2017-10-09)

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.

**Tags:** co.combinatorics, permutations
> **Comments:**
> **username_1**: When k=0 this is just finding a longest increasing subsequence which is easy. In general I'm less sure.  
> **username_0**: @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.  
> **username_0**: 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.  

---

## 0 answers

