Interval scheduling and colorful independent sets

René Van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

2 Citations (Scopus)


The NP-hard Independent Set problem is to determine for a given graph G and an integer κ whether G contains a set of κ 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.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
Number of pages10
Publication statusPublished - 31 Dec 2012
Externally publishedYes
Event23rd International Symposium on Algorithms and Computation, ISAAC 2012 - Taipei, Taiwan, Province of China
Duration: 19 Dec 201221 Dec 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7676 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd International Symposium on Algorithms and Computation, ISAAC 2012
CountryTaiwan, Province of China


Dive into the research topics of 'Interval scheduling and colorful independent sets'. Together they form a unique fingerprint.

Cite this