Parameterized complexity for the database theorist
Martin Grohe · ACM SIGMOD Record · 2002
Parameterized complexity theory provides a framework for a fine-grain complexity analysis of algorithmic problems that are intractable in general. In recent years, ideas from parameterized complexity theory have found their way into various areas of computer science, such as artificial intelligence [15], computational biology [1, 21], and, last but not least, database theory [16, 19].