Interval Scheduling and Colorful Independent Sets

Abstract Numerous applications in scheduling, such as resource allocation or steel manu-facturing, reduce to the NP-hard INDEPENDENT SET problem (given an undirected graph and an integer k, find a set of at least k pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which INDEPENDENT SET remains NP-hard but admits constant-factor approximations in polynomial time. We study the parameterized complexity of INDEPENDENT SET on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural “compactness ” parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are: 1. We show a complexity dichotomy: INDEPENDENT SET is polynomial-time solvable if both input interval graphs are cluster graphs, and NP-hard otherwise. 2. We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization). 3. We extend Halldórsson and Karlsson (2006)’s fixed-parameter algorithm for INDE-PENDENT SET on strip graphs parameterized by the structural parameter “maximum numbe