W[2]-hardness of Precedence Constrained K-Processor Scheduling

It is shown that the Precedence Constrained K-Processor Scheduling problem is hard for the parameterized complexity class W[2]. This means that there does not exist a constant c, such that for all fixed K, the Precedence Constrained k-Processor Scheduling problem can be solved in O(n^c) time, unless an unlikely collapse occurs in the parameterized complexity hierarchy. That is, if the problem can be solved in polynomial time for each fixed K, then it is likely that the degree of the running time polynomial must increase as the number of processors K increases.