Datengetriebene parametrisierte Algorithmik von Graphmodifikationsproblemen (DAPA)

• Antragsteller: Professor Dr. Rolf Niedermeier (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 210010251

• Erstellungsjahr: 2019

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

• 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter 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
  (Siehe online unter https://doi.org/10.1016/j.jcss.2017.08.002)