TY - GEN

T1 - Interval scheduling and colorful independent sets

AU - Van Bevern, René

AU - Mnich, Matthias

AU - Niedermeier, Rolf

AU - Weller, Mathias

PY - 2012/12/31

Y1 - 2012/12/31

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84871565797&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84871565797

SN - 9783642352607

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 247

EP - 256

BT - Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings

T2 - 23rd International Symposium on Algorithms and Computation, ISAAC 2012

Y2 - 19 December 2012 through 21 December 2012

ER -