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.