The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
For theoretical computer scientists, this work settles the parameterized complexity of long-standing open problems in scheduling and graph theory.
The paper establishes XNLP-completeness for Shuffle Product and Directed Bandwidth problems, resolving open parameterized complexity questions. It also derives implications for scheduling with precedence delays parameterized by graph width or maximum delay.
In this paper, we study the parameterized complexity of several variants of scheduling with precedence constraints between jobs. Namely, we consider the single machine setting with delay values on top of the precedence constraints. Such scheduling problems are related to several decades-old problems with open parameterized complexity status, notably Shuffle Product and Directed Bandwidth. We obtain XNLP-completeness results for both problems, and derive implications to scheduling with minimum (resp. maximum) delays parameterized by the width of the directed acyclic graph giving the precedence constraints, and/or by the maximum delay value in the input. Regarding Directed Bandwidth, we also settle the case of trees by showing XNLP-completeness parameterized by the target value. Beyond these results, we believe that Shuffle Product is an unusual and promising addition to the list of XNLP-complete problems.