Parameterized complexity: Exponential speed-up for planar graph problems

A parameterized problem is fixed parameter tractable if it admits a solving algorithm whose running time on input instance (I, k) is f(k) . \I \ (alpha), where f is an arbitrary function depending only on k. Typically, f is some exponential function, e.g., f (k) = c(k) for constant c. We describe general techniques to obtain growth of the form f (k) = c(rootk) for a large variety of planar graph problems. The key to this type of algorithm is what we call the "Layerwise Separation Property" of a planar graph problem. Problems having this property include PLANAR VERTEX COVER, PLANAR INDEPENDENT SET, and PLANAR DOMINATING SET.