|M.Sc Student||Wajc David|
|Subject||Parameterizing P: Proximity to Easy Variants|
|Department||Department of Computer Science||Supervisors||Professor Nir Ailon|
|Professor Hadas Shachnai|
|Professor 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)
nO(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 O(mn) ballpark for dense graphs (graphs with m=Omega(n2) edges) and all values of k, and improves upon this bound for any k << n. Our results imply that any proof of lower bounds for the time required to solve these problems must assume high parameter values.