Interval scheduling and colorful independent sets. (English) Zbl 1260.68167

van Bevern, René; Mnich, Matthias; Niedermeier, Rolf; Weller, Mathias

Chao, Kun-Mao (ed.) et al., Algorithms and computation. 23rd international symposium, ISAAC 2012, Taipei, Taiwan, December 19–21, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-35260-7/pbk). Lecture Notes in Computer Science 7676, 247-256 (2012).

Summary: The NP-hard Independent Set problem is to determine for a given graph \(G\) and an integer \(k\) whether \(G\) contains a set of \(k\) pairwise non-adjacent vertices. The problem has numerous applications in scheduling, including resource allocation and steel manufacturing. There, one encounters restricted graph classes such as 2-union graphs, which are edge-wise unions of two interval graphs on the same vertex set, or strip graphs, where additionally one of the two interval graphs is a disjoint union of cliques.
We prove NP-hardness of Independent Set on a very restricted subclass of 2-union graphs and identify natural parameterizations to chart the possibilities and limitations of effective polynomial-time preprocessing (kernelization) and fixed-parameter algorithms. Our algorithms benefit from novel formulations of the computational problems in terms of (list-)colored interval graphs.
For the entire collection see [Zbl 1258.68005].

MSC:

68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69	Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85	Graph algorithms (graph-theoretic aspects)
05C90	Applications of graph theory
90B35	Deterministic scheduling theory in operations research