Inductive $$k$$ k -independent graphs and c-colorable subgraphs in scheduling: a review
Matthias Bentert, René van Bevern, Rolf Niedermeier · Journal of Scheduling · 2018
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.