Parameterized Complexity Theory

• Main Authors: Flum, Jörg (Author), Grohe, Martin (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 2006.
• Series: Texts in Theoretical Computer Science. An EATCS Series
• Subjects: Computer science.; Architecture, Computer.; Computers.; Algorithms.; Mathematical logic.; Computer Science.; Computer System Implementation.; Mathematical Logic and Foundations.; Algorithm Analysis and Problem Complexity.; Theory of Computation.; Computation by Abstract Devices.; Mathematical Logic and Formal Languages.

Parameterized complexity theory is a recent branch of computational complexity theory that provides a framework for a refined analysis of hard algorithmic problems. The central notion of the theory, fixed-parameter tractability, has led to the development of various new algorithmic techniques and a...

Table of Contents:

• Fixed-Parameter Tractability
• Reductions and Parameterized Intractability
• The Class W[P]
• Logic and Complexity
• Two Fundamental Hierarchies
• The First Level of the Hierarchies
• The W-Hierarchy
• The A-Hierarchy
• Kernelization and Linear Programming Techniques
• The Automata-Theoretic Approach
• Tree Width
• Planarity and Bounded Local Tree Width
• Homomorphisms and Embeddings
• Parameterized Counting Problems
• Bounded Fixed-Parameter Tractability and Limited Nondeterminism
• Subexponential Fixed-Parameter Tractability.