An Introduction to Parameter­ized Algorithms

A lot of problems that matter in the real world are NP-hard, yet the instances that actually show up tend to have structure that input size alone does not capture. Parameterized algorithms measure running time in terms of both the input size and a second parameter (like the size of the solution being sought), and the goal is to confine the exponential blow-up to that parameter rather than to the whole input. I walk through the basic definitions of fixed-parameter tractability and a handful of core algorithmic techniques, using Feedback Vertex Set (breaking every cycle in a graph by deleting a small number of vertices) as a running example throughout.