## René van Bevern, Matthias Mnich, Rolf Niedermeier, and Mathias Weller.
Interval scheduling and colorful independent sets.
*Journal of Scheduling*, 18(5):449–469, 2015.

Numerous applications in scheduling, such as resource
allocation or steel manufacturing, can be modeled
using 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 ratio 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 as follows: 1. We show a complexity
dichotomy: restricted to graph classes closed under
induced subgraphs and disjoint unions, Independent Set
is polynomial-time solvable if both input interval
graphs are cluster graphs, and is 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 Independent Set
on strip graphs parameterized by the structural
parameter “maximum number of live jobs” to show that
the problem (also known as Job Interval Selection) is
fixed-parameter tractable with respect to the
parameter k and generalize their algorithm from strip
graphs to 2-union graphs. Preliminary experiments with
random data indicate that Job Interval Selection with
up to 15 jobs and 5⋅10^5 intervals can be solved
optimally in less than 5 min.

[ bib |
DOI |
source code |
http ]
Back

*This file was generated by
bibtex2html 1.98.*