Algorithm Engineering für NP-schwere Probleme: Parametrisierte Algorithmen versus etablierte Techniken

• Antragsteller: Dr. Falk Hüffner
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 230839996

• Erstellungsjahr: 2020

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

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