Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Interval scheduling and colorful independent sets. / van Bevern, René; Mnich, Matthias; Niedermeier, Rolf и др.
в: Journal of Scheduling, Том 18, № 5, 13.10.2015, стр. 449-469.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Interval scheduling and colorful independent sets
AU - van Bevern, René
AU - Mnich, Matthias
AU - Niedermeier, Rolf
AU - Weller, Mathias
PY - 2015/10/13
Y1 - 2015/10/13
N2 - Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer $$k$$k, find a set of at least $$k$$k pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which Independent Set remains $$\mathrm{NP}$$NP-hard but admits constant ratio approximations in polynomial time. We study the parameterized complexity of Independent Set on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural “compactness” parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are as follows:1.We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions, Independent Set is polynomial-time solvable if both input interval graphs are cluster graphs, and is (Formula presented.)-hard otherwise.2.We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization).3.We extend Halldórsson and Karlsson (2006)’s fixed-parameter algorithm for Independent Set on strip graphs parameterized by the structural parameter “maximum number of live jobs” to show that the problem (also known as Job Interval Selection) is fixed-parameter tractable with respect to the parameter (Formula presented.) and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that Job Interval Selection with up to 15 jobs and (Formula presented.) intervals can be solved optimally in less than 5 min.
AB - Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer $$k$$k, find a set of at least $$k$$k pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which Independent Set remains $$\mathrm{NP}$$NP-hard but admits constant ratio approximations in polynomial time. We study the parameterized complexity of Independent Set on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural “compactness” parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are as follows:1.We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions, Independent Set is polynomial-time solvable if both input interval graphs are cluster graphs, and is (Formula presented.)-hard otherwise.2.We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization).3.We extend Halldórsson and Karlsson (2006)’s fixed-parameter algorithm for Independent Set on strip graphs parameterized by the structural parameter “maximum number of live jobs” to show that the problem (also known as Job Interval Selection) is fixed-parameter tractable with respect to the parameter (Formula presented.) and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that Job Interval Selection with up to 15 jobs and (Formula presented.) intervals can be solved optimally in less than 5 min.
KW - 2-union graphs
KW - Interval graphs
KW - Job interval selection
KW - Parameterized complexity
KW - Strip graphs
UR - http://www.scopus.com/inward/record.url?scp=84941423548&partnerID=8YFLogxK
U2 - 10.1007/s10951-014-0398-5
DO - 10.1007/s10951-014-0398-5
M3 - Article
AN - SCOPUS:84941423548
VL - 18
SP - 449
EP - 469
JO - Journal of Scheduling
JF - Journal of Scheduling
SN - 1094-6136
IS - 5
ER -
ID: 22340205