Data-driven parameterized algorithmics of graph modification problems(DAPA)

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2017
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 210010251

• Final Report Year: 2019

Final Report Abstract

Datengetriebene Parametrisierung ist ein wirksames Mittel, um effiziente und exakte Algorithmen mit praktischer Relevanz für schwere Graphenmodifikationsprobleme zu entwickeln. Etliche der in den Anträgen beschriebenen Zielsetzungen wurden erreicht, und unsere Ergebnisse sind in der internationalen Forschungsgemeinde auf großes Interesse gestoßen. Im Folgenden stellen wir schlaglichtartig vier Hauptergebnisse des DAPA-Projekts dar: • Unser parametrisierter Algorithmus zum Aufzählen temporaler Cliquen ist auf großes Interesse in der Forschungsgemeinde gestoßen und hat uns dazu veranlasst ein neues DFG-Projekt, welches sich auf temporale Graphenprobleme fokussiert, zu starten. • Wir haben erfolgreich das Problem der kombinatorischen Merkmalselektion untersucht und konnten präzise Grenzen zwischen effizient lösbaren und schweren Instanzen beschreiben. • Wir haben diverse Problemstellungen im Bereich Routing untersucht und die parametrisierte Komplexität analysiert. Dies hat die stark im Operations Research verankerte „Arc-Routing“-Gemeinschaft nachhaltig auf das Thema der parametrisierten Komplexitätsanalyse aufmerksam gemacht. • Wir haben erfolgreich das gut motivierte Problem der h-Index-Manipulation untersucht und konnten neben unseren theoretischen Ergebnissen experimentell feststellen, dass h-Index-Manipulation in realen Zitationsnetzwerken effizient und wirksam möglich ist.

Publications

• Chapter 2: The complexity of arc routing problems. In Arc Routing: Problems, Methods, and Applications, pages 19–52. SIAM, 2013
  R. van Bevern, R. Niedermeier, M. Sorge, und M. Weller
  (See online at https://doi.org/10.1137/1.9781611973679.ch2)
• Towards optimal and expressive kernelization for d-hitting set. Algorithmica, 70(1):129–147, 2014
  R. van Bevern
  (See online at https://doi.org/10.1007/s00453-013-9774-3)
• Polynomial-time data reduction for the subset interconnection design problem. SIAM Journal on Discrete Mathematics, 29(1):1–25, 2015
  J. Chen, C. Komusiewicz, R. Niedermeier, M. Sorge, O. Suchý, und M. Weller
  (See online at https://doi.org/10.1137/140955057)
• H-index manipulation by merging articles: Models, theory, and experiments. Artificial Intelligence, 240:19–35, 2016
  R. van Bevern, C. Komusiewicz, R. Niedermeier, M. Sorge, und T. Walsh
  (See online at https://doi.org/10.1016/j.artint.2016.08.001)
• H-index manipulation by undoing merges. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI ’16), pages 895–903, 2016
  R. van Bevern, H. Molter, C. Komusiewicz, R. Niedermeier, M. Sorge, und T. Walsh
  (See online at https://doi.org/10.3233/978-1-61499-672-9-895)
• A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments. Networks, 70(3):262–278, 2017
  R. van Bevern, C. Komusiewicz, und M. Sorge
  (See online at https://doi.org/10.1002/net.21742)
• Adapting the Bron- Kerbosch algorithm for enumerating maximal cliques in temporal graphs. Social Network Analysis and Mining, 7(1):35:1–35:16, 2017
  A.-S. Himmel, H. Molter, R. Niedermeier, und M. Sorge
  (See online at https://doi.org/10.1007/s13278-017-0455-0)
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs. Journal of Computer and System Sciences, 92:22–47, 2018
  I. A. Kanj, C. Komusiewicz, M. Sorge, und E. J. van Leeuwen
  (See online at https://doi.org/10.1016/j.jcss.2017.08.002)