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

Abstract

Given a permutation π of {1,...,n} and a positive integer k, we give an algorithm with running time 2^{O(k2 log k)}n^O(1) that decides whether π can be partitioned into at most k increasing or decreasing subsequences. Thus we resolve affirmatively the open question of whether the problem is fixed parameter tractable. This NP-complete problem is equivalent to deciding whether the cochromatic number, partitioning into the minimum number of cliques or independent sets, of a given permutation graph on n vertices is at most k. In fact, we give a more general result: within the mentioned running time, one can decide whether the cochromatic number of a given perfect graph on n vertices is at most k.