Parameterized Approximation - new concepts and new applications

• Applicant: Professor Dr. Henning Fernau
• Subject Area: Theoretical Computer Science
• Term: from 2014 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 259237183

About 40 years ago, the notion of NP-hardness was developed. Many combinatorial problems were shown to be NP-hard. This means that they are supposed not to have efficient solving algorithms. More technically speaking, finding a deterministic polynomial-time algorithm for any of the NP-complete problems would entail having deterministic polynomial-time algorithms for all of them. It is generally believed that this is impossible, but hitherto no mathematical proof for this conjecture has been found. Actually, this question is one of the most important mathematical questions of our days.As NP-complete combininatorial problems often model questions that are important for practical applications, (at least) two algorithm development strategies have been suggested and investigated in (Theoretical) Computer Science: (a) Since nearly 50 years, polynomial-time algorithms have been developed that do not find optimal solutions to a given problem instance, but only approximative ones, but with a certain performance guarantee.(b) Since nearly 20 years, exact parameterized complexity offers an alternative approach, trying to restrict the seemingly inevitable combinatorial explosion of exact algorithms for NP-complete problems to a hopefully small part of the input, the so-called parameter.Both approaches have their limits that can be shown by complexity-theoretic means. This motivates to combine both approaches, leading to the idea of parameterized approximation, a field that started out in recent years.Yet, this idea is in its infancy. Within this project, we strive to find new ways for such algorithms. For instance, many polynomial-time approximation algorithms are based on Mathematical Optimization (most notably, Integer Linear Programming (ILP)), while this is not the case for parameterized algorithms, be them exact or approximative. It is natural to ask if or how ILP techniques can be used to develop parameterized approximation algorithms.Conversely, there are algorithmic ideas like iterative compression that are most important for exact parameterized algorithms, but that have not been used so far in a genuine fashion for parameterized approximation, which is another task we want to achieve.To solve these methodological questions, we will tackle concrete combinatorial problems.We want to focus on such problems from the area of Data Security. First, the importance of this area became much more clear in recent times, and secondly, no systematic study of the according combinatorial problems has been undertaken so far.With this grant, we like to pay one PhD student who has proven to be particularly eligible, as she studied two subjects, Computer Science and Mathematics. Both for the modeling aspect (in Data Security) and for the finding of exact and approximative algorithms, we ask for a Mercator fellow to help us in the project.

• DFG Programme: Research Grants