Algorithmics and Computational Complexity

More Efficient Algorithms for Polynomial-Time Solvable Graph Problems (FPTinP)

Synopsis

The central goal of this project is to extend the focus of parametrized algorithmics from NP-hard problems to polynomial-time solvable problems. This is motivated by the observation that polynomial-time algorithms with cubic running times are for many applications questionable at least; this is a fact that is particularly obvious in the context of Big Data.
In contrast, an algorithm with running in O(k^4 · n) time for some problem specific parameter can be much more desirable provided that k is much smaller than n in the application. Like in classical parameterized algorithmics, we want to focus on graph problems with polynomial-time algorithms using the rich arsenal of parameterized methods and techniques developed so far.

Funded by

Deutsche Forschungsgemeinschaft (Project FPTinP, NI 369/16)

Time

Since December 2017

Head: formerly Rolf Niedermeier, since 2022:

Organization name Algorithmics and Computational Complexity
Office TEL 5-1
Room TEL 509A
office hoursTuesdays 17:30 - 18:30

People