Many scheduling problems, even seemingly basic ones such as P2|chains|Cmax, have been proved (strongly) NP-hard over the years. This problem was even showed to remain weakly NP-hard with three chains. Upon reaching NP-hardness this quickly, it becomes difficult to establish anything deeper about these scheduling problems within the scope of classical com-plexity theory.

To answer this, parameterized complexity theory gives additional tools for a refined analysis of such hard scheduling problems. Given a parameter k and denoting n the input size, a problem is called fixed−parameter tractable (FPT) parameterized by k if it can be solved in time O(poly(n)×f(k)) with f an arbitrary function. The idea is to identify k as the limiting property and give a polynomial time algorithm for all instances with a bounded value of k. When the studied problem is believed to not be FPT, the W-hierarchy is usually used to evaluate its difficulty relative to the considered parameter. We have FPT=W[0]⊆W[1]⊆W[2]⊆etc. and unless P=NP, all the inclusions are believed to be strict.

While parameterized complexity theory has been successfully applied to a lot of computerscience areas, it has started to be studied extensively on scheduling only quite recently. The pathwidth - noted μ - which we define as the maximum number of overlapping job time windows at any given time, has recently received increasing interest. However to the best of our knowledge this parameter has had no hardness result relative to it proved yet. Such a result would help refining the frontier between which problems are FPT with this parameter and which ones are not.

We consider the decision problem with a single machine, chains as precendence relations, release dates, deadlines, unit time processing times and exact delays between consecutive nodes in a chain. We show that this problem is W[1]-hard parameterized by μ. We reduce from INDEPENDENT SET which is a well-known W[1]-complete problem parameterized by the size k of the independent set. The ideas behind this reduction have potential to be reinvested in other parameterized scheduling problems involving delays.