Algorithm Engineering for NP-hard Problems: Parameterized Algorithms versus Established Techniques

• Applicant: Dr. Falk Hüffner
• Subject Area: Theoretical Computer Science
• Term: from 2013 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 230839996

• Final Report Year: 2020

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
  
• 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
  
• 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ý