Room 327

A fine-grained approach for designing (time and space) efficient algorithms

Rajesh Chitnis

Weizmann Institute of Science , Rehovot, Israel

*Title*: A Fine-Grained Approach for Designing (Time and Space) Efficient
Algorithms

*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)·n^{O(1)} where f is a computable
function and n is the input size.

In the first part of the talk, I will describe some techniques for
designing optimal FPT and XP algorithms for cut and connectivity problems
on directed graphs.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.

The second part of the talk will be about some 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.