Interval scheduling and colorful independent sets

Abstract : TheNP-hardIndependentSetproblemistodeterminefora 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 encoun- ters 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 prepro- cessing (kernelization) and fixed-parameter algorithms. Our algorithms benefit from novel formulations of the computational problems in terms of (list-)colored interval graphs.
Document type :
Journal articles
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01349213
Contributor : Isabelle Gouat <>
Submitted on : Wednesday, July 27, 2016 - 8:19:18 AM
Last modification on : Friday, March 15, 2019 - 1:15:03 AM

File

interval-scheduling-and-colorf...
Files produced by the author(s)

Identifiers

Collections

Citation

René Van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller. Interval scheduling and colorful independent sets. Journal of Scheduling, Springer Verlag, 2015, 18 (5), pp.449-469. ⟨10.1007/s10951-014-0398-5⟩. ⟨lirmm-01349213⟩

Share

Metrics

Record views

748

Files downloads

369