M.Sc Thesis | |

M.Sc Student | Wajc David |
---|---|

Subject | Parameterizing P: Proximity to Easy Variants |

Department | Department of Computer Science |

Supervisors | ASSOCIATE PROF. Nir Ailon |

PROF. Hadas Shachnai | |

PROF. Joseph Naor | |

Full Thesis text |

The field of parameterized complexity
strives to solve intractable problems efficiently, via multivariate analysis of
running time, as a function of both the input size *n* and a parameter *k*.
Such analysis enables to show that some of these problems are *fixed
parameter tractable* (FPT); in other words, they can be solved in time *f(k)
n ^{O(1)}*. The rationale behind this approach is the observation
that many real-life inputs have small parameter values.

In this work we study multivariate analysis of running time for problems in P, to obtain faster algorithms for these problems. In particular, we

(i) present a framework for faster solutions for myriad shortest path problems, and

(ii) develop faster algorithms for maximum weight matching.

We parameterize the studied problems
by *k*, the number of vertices that need to be removed to obtain a graph
from an easier input class.

Our algorithms achieve the same
running times as algorithms for the easier input class for fixed values of *k*,
and significantly better than the best known algorithms for a wide range of
values of *k*. For example, we solve the single source shortest path
problem for graphs with *n* vertices and *m* edges having *k*
vertices with outgoing negative-weight edges in *O(k(m log n) ^{3})*
time. This running time is no slower than the state-of-the-art