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

DOI10.1007/S10951-018-0595-8MaRDI QIDQ2327955zbMATH OpenOpenAlexFDO

Authors Matthias Bentert, René van Bevern, Rolf Niedermeier

Publication date 8 October 2019

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.06481

zbMATH Keywords

chordal graphsindependent setinductive \(k\)-independent graphsinterval graphsjob interval selectionNP-hard problemsparameterized complexity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Deterministic scheduling theory in operations research (90B35) Programming involving graphs or networks (90C35)

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.

Recommendations

• Elimination graphs
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Approximation algorithms for intersection graphs
• Cluster graph modification problems
• Color-coding
• Complexity results for scheduling tasks with discrete starting times
• Correlation clustering
• Elimination graphs
• Fundamentals of parameterized complexity
• How well can graphs represent wireless interference?
• scientific article; zbMATH DE number 1185295 (Why is no real title available?)
• scientific article; zbMATH DE number 3513839 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 2065154 (Why is no real title available?)
• scientific article; zbMATH DE number 6783420 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Integrated sequencing and scheduling in coil coating
• Interval scheduling: A survey
• Line Graphs of Helly Hypergraphs
• Maximizing weighted number of just-in-time jobs on unrelated parallel machines
• Mutual exclusion scheduling
• Mutual exclusion scheduling with interval graphs or related classes. I
• New races in parameterized algorithmics
• On rigid circuit graphs
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Parameterized algorithms
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• Parameterized complexity of machine scheduling: 15 open problems
• Parametrized complexity theory.
• Recognizing d-interval graphs and d-track interval graphs
• Recognizing graphs with fixed interval number is NP-complete
• Reflections on multivariate algorithmics and problem parameterization
• Scheduling Interval-Ordered Tasks
• Scheduling jobs with fixed start and end times
• Strip Graphs: Recognition and Scheduling
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The LBFS structure and recognition of interval graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Tolerance intersection graphs on binary trees with constant tolerance 3
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Universal framework for wireless scheduling problems

Cited in

(14)

• Finding temporal paths under waiting time constraints
• Computing inductive vertex orderings
• Reconfiguration of colorable sets in classes of perfect graphs
• Conflict free feedback vertex set: a parameterized dichotomy
• Mathematical programming models and exact algorithms
• The Maximum k-Colorable Subgraph Problem and Related Problems
• Fixed interval scheduling with third‐party machines
• Finding Temporal Paths Under Waiting Time Constraints.
• Equitable scheduling on a single machine
• Literature reviews in operations research: a new taxonomy and a meta review
• A multivariate complexity analysis of the material consumption scheduling problem
• On the parameterized complexity of interval scheduling with eligible machine sets
• Hardness of interval scheduling on unrelated machines
• Counting temporal paths

This page was built for publication: Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2327955)