Jochen Alber, Henning Fernau, Rolf Niedermeier

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 ...
more >>>

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

We provide new upper bounds on the complexity of the s-t-connectivity problem in planar graphs, thereby providing additional evidence that this problem is not complete for NL. This also yields a new upper bound on the complexity of computing edit distance. Building on these techniques, we provide new upper bounds ... more >>>