Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

RSS-Feed




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


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