Publication:892898

DOI10.1007/978-3-642-35261-4_28zbMath1328.90065arXiv1402.0851OpenAlexW3101862638MaRDI QIDQ892898

Rolf Niedermeier, Matthias Mnich, Mathias Weller, René van Bevern

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

zbMATH Keywords

interval graphsparameterized complexity2-union graphsjob interval selectionstrip graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of graph theory (05C90) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Parameterizing by the number of numbers
• Random interval graphs
• Some simplified NP-complete graph problems
• Which problems have strongly exponential complexity?
• On the approximability of an interval scheduling problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Incidence matrices and interval graphs
• Parametrized complexity theory.
• Integrated Sequencing and Scheduling in Coil Coating
• The LBFS Structure and Recognition of Interval Graphs
• Complexity results for scheduling tasks with discrete starting times
• Strip Graphs: Recognition and Scheduling
• Interval scheduling: A survey
• Limits and Applications of Group Algebras for Parameterized Problems
• On Finding the Maxima of a Set of Vectors
• Graph Classes: A Survey
• Color-coding
• Kernelization Lower Bounds by Cross-Composition
• Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems
• Scheduling and Fixed-Parameter Tractability
• Scheduling Split Intervals
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)

Related Items (30)

Balanced independent and dominating sets on colored interval graphs ⋮ A general scheme for solving a large set of scheduling problems with rejection in FPT time ⋮ On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack ⋮ Tree Containment With Soft Polytomies ⋮ On data reduction for dynamic vector bin packing ⋮ Fixed interval scheduling with third‐party machines ⋮ Responsive strategic oscillation for solving the disjunctively constrained knapsack problem ⋮ A multivariate complexity analysis of the material consumption scheduling problem ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ A new perspective on single-machine scheduling problems with late work related criteria ⋮ Unnamed Item ⋮ On streaming algorithms for geometric independent set and clique ⋮ Winner determination in geometrical combinatorial auctions ⋮ Unnamed Item ⋮ Finding temporal paths under waiting time constraints ⋮ On the parameterized tractability of single machine scheduling with rejection ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Star Partitions of Perfect Graphs ⋮ Completing Partial Schedules for Open Shop with Unit Processing Times and Routing ⋮ Approximate search for known gene clusters in new genomes using PQ-trees ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Parameterized complexity of a coupled-task scheduling problem ⋮ Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes ⋮ On the parameterized complexity of interval scheduling with eligible machine sets ⋮ On the parameterized tractability of the just-in-time flow-shop scheduling problem ⋮ Serial batching to minimize the weighted number of tardy jobs ⋮ Unnamed Item ⋮ Scheduling meets \(n\)-fold integer programming ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review

This page was built for publication: Interval scheduling and colorful independent sets