W[2]-HARDNESS OF PRECEDENCE CONSTRAINED K-PROCESSOR SCHEDULING

It is shown that the Precedence Constrained K-Processor Scheduling pro blem is hard for the parameterized complexity class W[2]. This means t hat there does not exist a constant c, such that for all fixed K, the Precedence Constrained K-Processor Scheduling problem can be solved in 0(n(C)) time, unless an unlikely collapse occurs in the parameterized complexity hierarchy. That is, if the problem can be solved in polyno mial time for each fixed K, then it is likely that the degree of the r unning time polynomial must increase as the number of processors K inc reases.