Inductive k -independent graphs and c-colorable subgraphs in scheduling: a review

Matthias Bentert, René van Bevern, Rolf Niedermeier

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

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 languageEnglish
Pages (from-to)3-20
Number of pages18
JournalJournal of Scheduling
Volume22
Issue number1
DOIs
Publication statusPublished - 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

Fingerprint Dive into the research topics of 'Inductive k -independent graphs and c-colorable subgraphs in scheduling: a review'. Together they form a unique fingerprint.

Cite this