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.
Fichier principal
interval-scheduling-and-colorful-independent-sets-isaac12.pdf (300.96 Ko)
Télécharger le fichier
Origin | Files produced by the author(s) |
---|
Loading...