Preprint Poster doi abstract bibtex

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 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 Maximum c-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-inductive and inductive 2-inductive graphs with applications in scheduling.

@article{BBN19, author = {Matthias Bentert and Ren{\'{e}} van Bevern and Rolf Niedermeier}, journal = {Journal of Scheduling}, date = {2019-02-01}, title = {Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: A review}, year = 2019, doi = {10.1007/s10951-018-0595-8}, volume = {22}, number = 1, pages = {3--20}, url_Preprint = {https://arxiv.org/abs/1712.06481}, url_Poster = {https://www.researchgate.net/publication/342122158_Wireless_Scheduling_Graph_Classes_and_c-Colorable_Subgraphs}, abstract = {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 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 Maximum c-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-inductive and inductive 2-inductive graphs with applications in scheduling.} }

Downloads: 0