(Wireless) Scheduling, Graph Classes, and $c$-Colorable Subgraphs
Preprint
Abstract
Inductive $k$-independent graphs are a generalization of 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. On the contrary, 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-independent and inductive 2-independent graphs with applications in scheduling.
Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experimentsNetworks, 2017
- Parameterized Algorithms2015
- Fundamentals of Parameterized Complexity2013
- New Races in Parameterized AlgorithmicsLecture Notes in Computer Science, 2012
- Interval scheduling: A surveyNaval Research Logistics (NRL), 2007
- Strip Graphs: Recognition and Scheduling2006
- Parameterized Complexity Theory2006
- Scheduling Intervals Using Independent Sets in Claw-Free GraphsLecture Notes in Computer Science, 2003
- Opportunity Cost Algorithms for Combinatorial Auctions2002
- An Introduction to Chordal Graphs and Clique Trees1993