The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors
Rodney G. Downey, Michael R. Fellows, Michael Allen Langston · The Computer Journal · 2007
Parameterized complexity studies a generalization of the notion of polynomial time where, in addition to the overall input size n, one also considers the effects on computational complexity of a secondary measurement, the parameter. The central notion of the field is fixed-parameter tractability (FPT), which refers to solvability in time f(k)nc, where f is some function (usually exponential) of the parameter k, and c is a constant. The subject unfolds in two basic complementary projects and associated mathematical toolkits: (1) How to design (and improve) FPT algorithms, for parameterized problems that admit them and (2) How to gather evidence that a parameterized problem probably does not admit an FPT algorithm. There are several things that one can say about the field, in a general way. ... This Special Issue of surveys of various aspects of parameterized complexity and algorithmics began on the suggestion of the Editor-in-Chief, Fionn Murtagh, who after hearing a broad account of the field at a colloquium at Royal Holloway, University of London, declared, “This is a subject that every computer scientist should know about.”