ECCC-Report TR01-023https://eccc.weizmann.ac.il/report/2001/023Comments and Revisions published for TR01-023en-usThu, 11 Oct 2001 00:00:00 +0200
Revision 1
| Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems |
Jochen Alber,
Henning Fernau,
Rolf Niedermeier
https://eccc.weizmann.ac.il/report/2001/023#revision1Thu, 11 Oct 2001 00:00:00 +0200https://eccc.weizmann.ac.il/report/2001/023#revision1
Paper TR01-023
| Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems |
Jochen Alber,
Henning Fernau,
Rolf Niedermeier
https://eccc.weizmann.ac.il/report/2001/023A 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.
Tue, 13 Mar 2001 20:02:51 +0200https://eccc.weizmann.ac.il/report/2001/023