Executive Summary : | Network design problems are a prominent and well-studied class problems in computer science, motivated by numerous practical applications as well as strong theoretical interest. They are very well studied in approximation algorithms and combinatorial optimization. Most problems in this class are unfortunately NP-hard, and therefore we don’t expect (time-)efficient algorithms that can solve them optimally. They have therefore been extensively studied in Approximation algorithms, where we design efficient algorithms that compute approximately optimal solutions. This project focuses on studying network design problems in the framework of Parameterized Complexity. In this framework, we attempt to exploit various structural properties of the problem instances to design efficient algorithms that solve them optimally. For example, we can obtain algorithms that determine that either compute a solution of cost k, or no such solution exists. The runtime of such algorithms will depend on k, which is usually a bounded number. Hence such algorithms can often solve real-world instances in a reasonable amount of time. The parameterized complexity of network design problems is not fully explored. There have been a few results on some of the basic problems in this category (details are presented in the attached technical document). Some of these results have provided new insights into these problems that were useful beyond parameterized complexity. The main aim of this project is to conduct a systematic study of the parameterized complexity of network design problems. In particular, we would focus on “Connectivity Augmentation Problems” and “Vertex Connectivity Network Design” problems during this project. It will involve developing new tools and techniques for these problems that are likely to find applications elsewhere. We remark that past research in this direction (including our own) has led to publications in top venues of computer science. We expect that resolving some of the main open questions of this project will also result in high impact publications, that lead to follow-up research and applications. We refer to the attached technical document for more details on this project. |