10:30--11:45, Seminar Hall
The Parameterized Complexity of Network Design Problems
Pranabendu Misra
University of Bergen.
04-01-19

---

Abstract

Network Design Problems, which concern designing minimum cost networks that satisfy a given set of connectivity constraints, 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 algorithms. Parameterized Complexity is a different framework for dealing with computational intractability, 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. This includes problems such as Steiner Tree, Connectivity Augmentation, Minimum Equivalent Graph and several others. This talk is based on results that has appeared in SODA 18, WADS 17,ICALP 14 and some recent unpublished work.

A first undergraduate course in Algorithms should be enough background to understand most of the talk.