Revision #1 Authors: Jochen Alber, Henning Fernau, Rolf Niedermeier

Accepted on: 11th October 2001 00:00

Downloads: 1772

Keywords:

TR01-023 Authors: Jochen Alber, Henning Fernau, Rolf Niedermeier

Publication: 13th March 2001 20:02

Downloads: 1915

Keywords:

A parameterized problem is called fixed parameter tractable

if it admits a solving algorithm whose running time on

input instance $(I,k)$ is $f(k) \cdot |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 some

constant $c$.

We describe general techniques to obtain then growth of the

form $f(k)=c^{\sqrt{k}}$ 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, or planar dominating set. Extensions

of our speed-up technique to basically all fixed parameter

tractable planar graph problems are also exhibited.

Moreover, on our way to design fixed parameter algorithms with

sublinear exponents, we derive some theoretical results

relating, e.g. the domination number or the vertex cover number,

with the treewidth of a plane graph.