View article

We look at the basics of parameterized complexity. This is a method which seeks to find tractability by limiting some parameter in the input. We analyse methods for proving parameterized tractability and also give some basic results the completeness and hardness theory. We also look at limitations of the methods and XP-optimality. The latter gives methods for proving various algorithms are more or less optimal, subject to complexity considerations.