Fixed-parameter tractability and logic
J. Flum, Martin Grohe · arXiv (Cornell University) · 1999
We exhibit a close connection between parameterized complexity theory and logic. Our approach is that of descriptive complexity theory. We study the definability of parameterized problems and try to obtain information about the parameterized complexity of the problems through the syntactical structure of the defining sentences. On the one hand, we use this approach to prove that certain problems are fixed-parameter tractable because they can be defined by syntactically simple formulas. On the other hand, we characterize classes of intractable problems by syntactical means.