Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization

Given a permutation π   of {1,…,n}{1,…,n} and a positive integer k, can π be partitioned into at most k   subsequences, each of which is either increasing or decreasing? We give an algorithm with running time 2O(k2logk)nO(1)2O(k2logk)nO(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 2O(k2logk)nlogn 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.