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)

Abstract

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
Pages247-256
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

Conference

Conference23rd International Symposium on Algorithms and Computation, ISAAC 2012
CountryTaiwan, Province of China
CityTaipei
Period19.12.201221.12.2012

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

Cite this