Summary: Given a permutation \(\pi\) of \(\{1,\dots,n\}\) and a positive integer \(k\), can \(\pi\) be partitioned into at most \(k\) subsequences, each of which is either increasing or decreasing? We give an algorithm with running time \(2^{O(k^2\log k)}n^{O(1)}\) that solves this problem, thereby showing that it is fixed parameter tractable. This NP-complete problem is equivalent to deciding whether the cochromatic number of a given permutation graph on \(n\) vertices is at most \(k\). Our algorithm solves in fact a more general problem: within the mentioned running time, it decides whether the cochromatic number of a given perfect graph on \(n\) vertices is at most \(k\).
To obtain our result we use a combination of two well-known techniques within parameterized algorithms: iterative compression and greedy localization. Consequently we name this combination “iterative localization”. We further demonstrate the power of this combination by giving an algorithm with running time \(2^{O(k^2\log k)}n\log n\) that decides whether a given set of \(n\) non-overlapping axis-parallel rectangles can be stabbed by at most \(k\) of a given set of horizontal and vertical lines.