#### Alladi Ramakrishnan Hall

#### Parameterized Complexity of Network Design Problems

#### Pranabendu Misra

##### University of Bergen

*Network Design Problems, which concern designing minimum cost networks that satisfy given set of connectivity constrains'', *

are very well studied in computer science and combinatorial optimization. Almost all these problems are NP-hard, and a number of results are known about them in the realm of approximation algorihms.

Parameterized Complexity is a different framework for dealing with computational intractibility, where typically we try to design fast algorithms to solve the problem on those instances which admit a ``small cost solution''. In this talk we will discuss some recent results on the parameterized complexity of network design problems.

Done