אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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 \emph{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 having k vertices with outgoing negative-weight edges in O(k(m+n log n)+k^3) time. This running time is no slower than the state-of-the-art O(mn) ballpark for dense graphs (graphs with m=\Omega(n^2) 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.