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 appeared in SODA 18, WADS 17, ICALP 14 and some recent unpublished work.Discipline/Coordinating Entity: Computer Science and Engineering