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

Given a permutation π of { 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 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.

Authors

• Pinar Heggernes
• Dieter Kratsch
• Daniel Lokshtanov
• Venkatesh Raman
• Saket Saurabh

Keywords

No keywords are indexed for this paper.