#### 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.

Done