Contributions to Parameterized Complexity

Abstract

This thesis is presented in two parts. In Part I we concentrate on algorithmic aspects of parameterized complexity. We explore ways in which the concepts and algorithmic techniques of parameterized complexity can be fruitfully brought to bear on a (classically) well-studied problem area, that of scheduling problems modelled on partial orderings. We develop efficient and constructive algorithms for parameterized versions of some classically intractable scheduling problems. We demonstrate how different parameterizations can shatter a classical problem into both tractable and (likely) intractable versions in the parameterized setting; thus providing a roadmap to efficiently computable restrictions of the original problem. We investigate the effects of using width metrics as restrictions on the input to online problems. The online nature of scheduling problems seems to be ubiquitous, and online situations often give rise to input patterns that seem to naturally conform to restricted width metrics. However, so far, these ideas from topological graph theory and parameterized complexity do not seem to have penetrated into the online algorithm community. Some of the material that we present in Part I has been published in [52] and [77]. In Part II we are oriented more towards structural aspects of parameterized complexity. Parameterized complexity has, so far, been largely confined to consideration of computational problems as decision or search problems. We introduce a general framework in which one may consider parameterized counting problems, extending the framework developed by Downey and Fellows for decision problems. As well as introducing basic definitions for tractability and the notion of a parameterized counting reduction, we also define a basic hardness class, #W[1], the parameterized analog of Valiant's class #P. We characterize #W[1] by means of a fundamental counting problem, #SHORT TURING MACHINE ACCEPTANCE, which we show to be complete for this class. We also determine #W[1]-completeness, or #W[l]-hardness, for several other parameterized counting problems. Finally, we present a normalization theorem, reworked from the framework developed by Downey and Fellows for decision problems, characterizing the #W[t],(t є N). parameterized counting classes. Some of the material that we present in Part II has been published in [78].