Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR01-023 | 11th October 2001 00:00

#### Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

Revision #1
Authors: Jochen Alber, Henning Fernau, Rolf Niedermeier
Accepted on: 11th October 2001 00:00
Downloads: 1370
Keywords:

Abstract:

### Paper:

TR01-023 | 13th March 2001 00:00

#### Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

TR01-023
Authors: Jochen Alber, Henning Fernau, Rolf Niedermeier
Publication: 13th March 2001 20:02
Downloads: 1460
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint