The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth

Hans L. Bodlaender, Maher Mallem (🖂) · 2026

Read The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth by Hans L. Bodlaender, Maher Mallem (🖂) (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03727.txt.

Introduction

Hans L. Bodlaender and Maher Mallem study scheduling problems where jobs have precedence constraints plus minimum or maximum delays between them. Such problems connect to two decades-old questions with open parameterized complexity status: Shuffle Product and Directed Bandwidth. Parameterized complexity asks whether problems become tractable when some structural parameter is small.

The authors prove XNLP-completeness for both problems, a strong hardness classification within the parameterized hierarchy. Consequences follow for scheduling parameterized by the width of the precedence graph or by the largest delay. For Directed Bandwidth on trees, they also settle XNLP-completeness parameterized by the target value. They suggest Shuffle Product is an unusual, promising addition to the list of XNLP-complete problems.

Catalog record

CREATORHans L. Bodlaender, Maher Mallem (🖂)
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.03727

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth Thanks: An extended abstract of this paper appears in the proceedings of the 37th International Workshop on Combinatorial Algorithms, IWOCA 2026. Hans L. Bodlaender, Maher Mallem (🖂) Abstract 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. 1 Introduction In this paper, we study the parameterized complexity of several scheduling problems where there are precedence constraints with delays between jobs. Such delays are handy in that they can model a wide range of real-life problems. For instance, minimum delays mimic how instructions are handled in pipelined processors [ 7 ] , and maximum delays can model products of short shelf life. Even theoretically speaking, several decades-old problems with open parameterized complexity status like Unary Bin Packing [ 17 ] and Directed Bandwidth [ 6 ] are equivalent to scheduling settings with precedence delays - more on this in the later sections. Several of the problems studied in this paper have the same complexity: they are known to be in the class XP — that is, for each fixed value of the parameter, there is a polynomial time algorithm, but the exponent of the polynomial grows when the parameter grows, and the problems are not known to be fixed-parameter tractable. For many problems, the precise complexity is unknown. In this paper, we show that several parameterized scheduling problems with precedence constraints and delays are complete for a complexity class now known as XNLP. The class XNLP was originally introduced by Elberfeld et al. [ 10 ] , and renamed to XNLP by Bodlaender et al. [ 3 ] . In [ 3 ] , several problems were shown to be complete for this class, including Scheduling Of Jobs With Precedence Constraints with both the number of machines and the width of the precedence graph as parameters — the first example where a scheduling problem was shown to be XNLP-complete. Other recent work that shows that scheduling problems are complete for the class XNLP or for the related class XALP [ 2 ] can be found in [ 4 , 21 ] . Showing that a problem is XNLP-complete is interesting for several reasons: it pinpoints the exact complexity class of the problem and, assuming a conjecture by Pilipczuk and Wrochna [ 23 ] , we have that there is no algorithm in XP for the problem that uses only f(k)n^{O(1)} space — indeed, about all known XP algorithms for these problems employ dynamic programming and have space usage of \Omega\left(n^{f(k)}\right) for f a divergent function. Also, XNLP-hardness implies hardness for all classes W[i] with i positive integer (e.g., see Lemma 2 in [ 3 ] ). Among the several parameterized problems whose complexity we resolve by showing XNLP-completeness, we have the Shuffle Product problem. Given a target word t and source words s_{1},\ldots,s_{k} , one asks whether t can be obtained by interleaving the letters of s_{1},\ldots,s_{k} , while keeping the order of the letters from the original words. We strengthen the W[2]-hardness proof for Shuffle Product from [ 27 ] to XNLP-completeness (Section 3.1 ). We believe that this result is of independent interest, as Shuffle Product can be used as the starting point for several XNLP-hardness proofs. From this result, in Section 3.2 , we notably derive XNLP-completeness of single machine scheduling with precedence constraints, constant minimum delays and processing time at most two parameterized by the width of the directed acyclic graph. In Section 4 , we show XNLP-completeness of a scheduling problem with precedence constraints and maximum delays, namely the single machine scheduling of unit-time jobs under precedence constraints with equal maximum delays. This problem is equivalent to the directed variant of the well studied Bandwidth problem. Formulating it as a graph problem, we are given in the Directed Bandwidth problem a directed acyclic graph, and ask for a topological ordering f with for each arc vw , f(v)<f(w) and f(w)-f(v)\leq k for some target value k . We give two XNLP-completeness results for Directed Bandwidth in Section 4 , namely for general directed acyclic graphs with both the target bandwidth and the width as parameters, and for directed trees with the target bandwidth as parameter. Problem Section Parameter Result (Binary) Shuffle Product 3.1 number of XNLP-complete source words Directed Bandwidth 4.1 target value XNLP-complete for plus width directed acyclic graphs 4.2 target value XNLP-complete for directed trees Table 1: Summary of our main results. Connections between Shuffle Product and scheduling with minimum precedence delays are discussed in Section 3.2 . Directed Bandwidth is equivalent to single machine scheduling of unit-time jobs with equal-length maximum precedence delays - see the beginning of Section 4 . Our main results are summarized in Table 1 . In many cases, we improve upon or complement existing results. We delay the discussion of related literature to the separate sections. Figure 1 summarizes the XNLP-hardness reductions proposed in this paper. 2 Preliminaries 2.1 Definitions Given two integers a,b , [a,b] denotes set \{a,a+1,\ldots,b\} . Graphs. We assume the reader to be familiar with standard notions from graph theory. Throughout the paper, given a graph G , n denotes the number of vertices of G . We consider two types of directed trees: downwards directed trees, where each arc is directed from a vertex to one of its children, and upward directed trees, where each arc is directed from a vertex to its parent. Note that a hardness proof for one of these two trees directly transforms to a hardness proof for the other type, by reversing the direction of all arcs. Scheduling. The goal of scheduling is to complete a set of jobs over time under a set of constraints. Unless otherwise stated, n is the number of jobs, \mathcal{J}=[1,n] is the set of jobs and G_{prec}=(\mathcal{J},A) is a directed acyclic graph representing precedence constraints between jobs. Given two jobs i,j\in\mathcal{J} , if ij is an arc in G_{prec} then job i must be completed before job j is started. For the sake of simplicity, we restrict ourselves to the parallel identical machine setting, where m machines are available to execute jobs. Each machine can execute at most one job at a time. In our base setting, every job takes unit time to be processed. The formal definition is the following: Scheduling Of Jobs With Precedence Constraints Given: positive integers n,m,D and a directed acyclic graph G_{prec} . Question: is there a schedule completing all

Read the complete text