Algorithm Engineering for NP-hard Problems: Parameterized Algorithms versus Established Techniques
Final Report Abstract
Parameterized complexity is an approach for solving difficult combinatorial problems that tries to exploit the structure of real-world instances. The idea is to measure structural complexity by a parameter and to try to confine the combinatorial explosion to the parameter, such that instances can be solved quickly whenever the parameter is small. So far, most research is theoretical, and few experimental results are available. In this project, a large number of practically motivated problems were analyzed using the parameterized complexity framework, aiming to close the gap between theory and practice. These problems are from a wide range of applications such as finding structure in biological networks or forming teams to solve a task based on skills. We found strong support for the claim that the variety of parameters opens many avenues to tackling one particular problem (unlike approaches such as approximation algorithms). Typically, we found perhaps five parameters that seemed promising even without assuming too particular instance structure, and many of those allowed tractable algorithms. In several cases, experiments demonstrated that parameterized algorithms can optimally solve instances for which otherwise only heuristics were available. Typically, the most important tools were data reduction and kernelization (shrinking the instance until its size depends only on the parameter). In particular since these techniques can be combined with other approaches, this seems like a good direction for future experimental research on parameterized algorithms.
Publications
- Multivariate algorithmics for NP-hard string problems. Bulletin of the EATCS, 114:31–73, 2014
L. Bulteau, F. Hüffner, C. Komusiewicz, and R. Niedermeier
- Partitioning biological networks into highly connected clusters with maximum edge coverage. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 11(3):455–467, 2014
F. Hüffner, C. Komusiewicz, A. Liebtrau, and R. Niedermeier
(See online at https://doi.org/10.1109/TCBB.2013.177) - A graph modification approach for finding core–periphery structures in protein interaction networks. Algorithms for Molecular Biology, 10(1):13, 2015
S. Bruckner, F. Hüffner, and C. Komusiewicz
(See online at https://doi.org/10.1186/s13015-015-0043-7) - Fixed-parameter algorithms for DAG partitioning. Discrete Applied Mathematics, 220:134–160, 2017
R. van Bevern, R. Bredereck, M. Chopin, S. Hartung, F. Hüffner, A. Nichterlein, and O. Suchý
(See online at https://doi.org/10.1016/j.dam.2016.12.002)
