12:00, Seminar Hall
A Fine-Grained Approach for Designing (Time and Space) Efficient Algorithms
Rajesh Chitnis
Weizmann Institute of Science, Rehovot, Israel.
04-01-17

---

Abstract

The classical approach for designing algorithms measures the time complexity only as a measure of the input size. In the 90's, Downey and Fellows proposed a fine-grained approach for NP-hard problems: one or more parameters of the input instance are defined, and we investigate the effect of these parameters on the running time. The goal is to design algorithms that work efficiently if the parameters of the input instance are small, even if the size of the input is large. Formally, a problem is said to be fixed-parameter tractable (FPT) with respect to parameter k if the problem can be solved in time f(k)ﾃAﾂｷn^{O(1)} where f is a computable function and n is the input size.

In the first part of the talk, I will give a brief overview of FPT algorithms. This active area of research has seen many new developments over the last few years. The standard techniques for designing FPT algorithms on undirected graphs such as bidimensionality, treewidth-based dynamic programming, etc. seem to break down for directed graphs. I will present some of my work which overcomes this barrier, and designs optimal FPT and XP algorithms for cut and connectivity problems on directed graphs.

In the second part of the talk, I will present my recent work on parameterized streaming algorithms. For the Maximum Matching problem, I will describe optimal streaming algorithms in various streaming models such as insertion-only, promised and general insertion-deletion.