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 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.
Original language | English |
---|---|
Pages (from-to) | 3-20 |
Number of pages | 18 |
Journal | Journal of Scheduling |
Volume | 22 |
Issue number | 1 |
DOIs | |
Publication status | Published - 15 Feb 2019 |
Keywords
- Chordal graphs
- Independent set
- Inductive k-independent graphs
- Interval graphs
- Job interval selection
- NP-hard problems
- Parameterized complexity
- PARAMETERIZED COMPLEXITY
- INTERVAL-GRAPHS
- NUMBER
- RECOGNITION
- MULTIVARIATE ALGORITHMICS
- JOBS
OECD FOS+WOS
- 5.02.PE OPERATIONS RESEARCH & MANAGEMENT SCIENCE
- 2.11.IK ENGINEERING, MANUFACTURING
- 2.11.IF ENGINEERING, MULTIDISCIPLINARY