TY - JOUR

T1 - Inductive k -independent graphs and c-colorable subgraphs in scheduling

T2 - a review

AU - Bentert, Matthias

AU - van Bevern, René

AU - Niedermeier, Rolf

N1 - Publisher Copyright: © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2019/2/15

Y1 - 2019/2/15

N2 - Inductive k-independent graphs generalize chordal graphs and have recently been advocated in the context of interference-avoiding wireless communication scheduling. The NP-hard problem of finding maximum-weight induced c-colorable subgraphs, which is a generalization of finding maximum independent sets, naturally occurs when selecting c sets of pairwise non-conflicting jobs (modeled as graph vertices). We investigate the parameterized complexity of this problem on inductive k-independent graphs. We show that the Maximum Independent Set problem is W[1]-hard even on 2-simplicial 3-minoes—a subclass of inductive 2-independent graphs. In contrast, we prove that the more general Max-Weightc-Colorable Subgraph problem is fixed-parameter tractable on edge-wise unions of cluster and chordal graphs, which are 2-simplicial. In both cases, the parameter is the solution size. Aside from this, we survey other graph classes between inductive 1 -independent and inductive 2 -independent graphs with applications in scheduling.

AB - Inductive k-independent graphs generalize chordal graphs and have recently been advocated in the context of interference-avoiding wireless communication scheduling. The NP-hard problem of finding maximum-weight induced c-colorable subgraphs, which is a generalization of finding maximum independent sets, naturally occurs when selecting c sets of pairwise non-conflicting jobs (modeled as graph vertices). We investigate the parameterized complexity of this problem on inductive k-independent graphs. We show that the Maximum Independent Set problem is W[1]-hard even on 2-simplicial 3-minoes—a subclass of inductive 2-independent graphs. In contrast, we prove that the more general Max-Weightc-Colorable Subgraph problem is fixed-parameter tractable on edge-wise unions of cluster and chordal graphs, which are 2-simplicial. In both cases, the parameter is the solution size. Aside from this, we survey other graph classes between inductive 1 -independent and inductive 2 -independent graphs with applications in scheduling.

KW - Chordal graphs

KW - Independent set

KW - Inductive k-independent graphs

KW - Interval graphs

KW - Job interval selection

KW - NP-hard problems

KW - Parameterized complexity

KW - PARAMETERIZED COMPLEXITY

KW - INTERVAL-GRAPHS

KW - NUMBER

KW - RECOGNITION

KW - MULTIVARIATE ALGORITHMICS

KW - JOBS

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

U2 - 10.1007/s10951-018-0595-8

DO - 10.1007/s10951-018-0595-8

M3 - Article

AN - SCOPUS:85061908379

VL - 22

SP - 3

EP - 20

JO - Journal of Scheduling

JF - Journal of Scheduling

SN - 1094-6136

IS - 1

ER -