Interval scheduling and colorful independent sets
From MaRDI portal
Publication:892898
DOI10.1007/978-3-642-35261-4_28zbMATH Open1328.90065arXiv1402.0851OpenAlexW3101862638MaRDI QIDQ892898FDOQ892898
Authors: René van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller 
Publication date: 12 November 2015
Published in: Journal of Scheduling, Algorithms and Computation (Search for Journal in Brave)
Abstract: Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer k, find a set of at least k pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which Independent Set remains NP-hard but admits constant-ratio approximations in polynomial time. We study the parameterized complexity of Independent Set on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural "compactness" parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are: 1. We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions, Independent Set is polynomial-time solvable if both input interval graphs are cluster graphs, and is NP-hard otherwise. 2. We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization). 3. We extend Halld'orsson and Karlsson (2006)'s fixed-parameter algorithm for Independent Set on strip graphs parameterized by the structural parameter "maximum number of live jobs" to show that the problem (also known as Job Interval Selection) is fixed-parameter tractable with respect to the parameter k and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that Job Interval Selection with up to fifteen jobs and 5*10^5 intervals can be solved optimally in less than five minutes.
Full work available at URL: https://arxiv.org/abs/1402.0851
Recommendations
- Interval scheduling and colorful independent sets
- Interval colorings of graphs—Coordinated and unstable no‐wait schedules
- A note to independent sets in scheduling
- Extensions of coloring models for scheduling purposes
- scientific article; zbMATH DE number 1594564
- Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules
- scientific article; zbMATH DE number 7203465
- Scheduling Problems and Mixed Graph Colorings
- Interval edge-coloring: A model of curriculum scheduling
Applications of graph theory (05C90) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Fundamentals of parameterized complexity
- Graph Classes: A Survey
- Which problems have strongly exponential complexity?
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Incidence matrices and interval graphs
- Parametrized complexity theory.
- Title not available (Why is that?)
- Limits and Applications of Group Algebras for Parameterized Problems
- Color-coding
- Lower bounds based on the exponential time hypothesis
- Title not available (Why is that?)
- Title not available (Why is that?)
- Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
- Some simplified NP-complete graph problems
- On Finding the Maxima of a Set of Vectors
- Kernelization Lower Bounds by Cross-Composition
- Interval scheduling: A survey
- Scheduling Split Intervals
- Random interval graphs
- On the approximability of an interval scheduling problem
- Parameterizing by the number of numbers
- The LBFS structure and recognition of interval graphs
- Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- Title not available (Why is that?)
- Integrated sequencing and scheduling in coil coating
- Scheduling and Fixed-Parameter Tractability
- Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
- Complexity results for scheduling tasks with discrete starting times
- Strip Graphs: Recognition and Scheduling
Cited In (35)
- Completing Partial Schedules for Open Shop with Unit Processing Times and Routing
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- A multivariate complexity analysis of the material consumption scheduling problem
- Balanced independent and dominating sets on colored interval graphs
- On the parameterized tractability of single machine scheduling with rejection
- Interval scheduling and colorful independent sets
- On the parameterized complexity of interval scheduling with eligible machine sets
- Strip Graphs: Recognition and Scheduling
- Mutual exclusion scheduling with interval graphs or related classes. I
- Scheduling meets \(n\)-fold integer programming
- Parameterized complexity of machine scheduling: 15 open problems
- Title not available (Why is that?)
- On data reduction for dynamic vector bin packing
- A general scheme for solving a large set of scheduling problems with rejection in FPT time
- Finding Temporal Paths Under Waiting Time Constraints.
- A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
- Fixed interval scheduling with third‐party machines
- Interval edge-coloring: A model of curriculum scheduling
- Parameterized complexity of a coupled-task scheduling problem
- A new perspective on single-machine scheduling problems with late work related criteria
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- Tree Containment With Soft Polytomies
- Extensions of coloring models for scheduling purposes
- On the parameterized tractability of the just-in-time flow-shop scheduling problem
- Title not available (Why is that?)
- Approximate search for known gene clusters in new genomes using PQ-trees
- Title not available (Why is that?)
- Serial batching to minimize the weighted number of tardy jobs
- Polynomial-time data reduction for weighted problems beyond additive goal functions
- Winner determination in geometrical combinatorial auctions
- Responsive strategic oscillation for solving the disjunctively constrained knapsack problem
- Star Partitions of Perfect Graphs
- Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
- Finding temporal paths under waiting time constraints
- On streaming algorithms for geometric independent set and clique
This page was built for publication: Interval scheduling and colorful independent sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q892898)
