Beyond NP-completeness for problems of bounded width (extended abstract)
Hans L. Bodlaender, Michael R. Fellows, Michael T. Hallett · 1994
The parameterized computational complexity of a collection of well-known problems including: BAND-WIDTH, PRECEDENCE CONSTRAINED MULTIPROCES-SOR SCHEDULING, LONGEST COMMON SUBSEQUENCE, DNA PHYSICAL MAPPING (or INTERNALIZING COL-ORED GRAPHS), PERFECT PHYLOGENY (or TRIANGU-LATING COLORED GRAPHS), COLORED CUTWIDTH, and FEASIBLE REGISTER ASSIGNMENT is explored.It is shown that these problems are hard for various levels of the W hierarchy.In the case of PRECEDENCE CONSTRAINED MULTIPROCESSOR SCHEDULING the results can be interpreted as providing substantial new complexity lower bounds on the outcome of [OPEN 8] of the Garey and Johnson list.