Fast parametrized algorithms for directed graph problems

• Applicant: Dr. Paul Bonsma
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 121957638

NP-hard problems can not be solved efficiently in full generality at the moment, and it is widely believed that this situation will not change. There is however still the need to solve these problems in practice. Parameterized algorithms have been developed in the last two decades as a way of solving such computationally hard problems, by exploiting additional structural properties of problem instances as they may occur in practice. For problems on undirected graphs, much progress has been made, and many standard techniques are available. For directed graphs, very few results were known until recently. In the last two years, activity in this field has significantly increased and a few breakthrough results have been obtained. However, the recent algorithms are still far from practical, and are mostly obtained by problem-specific methods. The proposed research aims to address both issues, by developing faster algorithms for some central and important problems, and by developing structural tools for directed graphs that can be applied to a wide variety of problems. The research is also expected to yield results in related areas such as approximation algorithms, structural and extremal graph theory.

• DFG Programme: Research Grants