Wechselwirkungen bei parametrisierter Datenreduktion

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

• Erstellungsjahr: 2021

Zusammenfassung der Projektergebnisse

Unsere verschiedenen Erkenntnisse zeigen, dass es noch viele wichtige und aussichtsreiche Facetten der Kernelisierungsforschung gibt. Wir haben die (auch praktische) Stärke von approximativen Kernelisierungen gesehen, die Subtilität des Umgangs mit gewichteten Problemen (in der Tat sind gewichtete Probleme in realen Anwendungen ziemlich häufig), die Perspektiven der partiellen Kernelisierung, die Stärken und Grenzen von Turing-Kernen und die wichtige Rolle des Parameters Lebensdauer im Zusammenhang mit der Kernelisierung von Problemen auf temporalen Graphen. Heutzutage ist die Suche nach (Polynomialzeit-) Datenreduktionsregeln eine gut etablierte wissenschaftliche Herausforderung wenn es um die algorithmische Bewältigung NP-schwerer Probleme geht – sowohl aus theoretischer als auch aus praktischer Sicht. Unser Projekt hat dazu beigetragen, die Grundlagen der Kernelisierung weiter zu erforschen und zu erweitern. Wie wir beschrieben haben, gibt es noch viele Möglichkeiten zur Forschung für zukünftige Arbeiten. Wir glauben, dass unsere Arbeit dafür den Weg geebnet und einige davon identifiziert hat.

Projektbezogene Publikationen (Auswahl)

• Multistage vertex cover. In Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC’19), volume 148 of LIPIcs, pages 14:1–14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019
  T. Fluschnik, R. Niedermeier, V. Rohm, and P. Zschoche
  (Siehe online unter https://doi.org/10.4230/LIPIcs.IPEC.2019.14)
• Polynomialtime preprocessing for weighted problems beyond additive goal functions. 2019
  M. Bentert, R. van Bevern, T. Fluschnik, A. Nichterlein, and R. Niedermeier
  (Siehe online unter https://doi.org/10.48550/arXiv.1910.00277)
• Multistage committee election. 2020
  R. Bredereck, T. Fluschnik, and A. Kaczmarczyk
  (Siehe online unter https://doi.org/10.48550/arXiv.2005.02300)
• Multistage s-t path: Confronting similarity with dissimilarity in temporal graphs. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC’20), volume 181 of LIPIcs, pages 43:1–43:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020
  T. Fluschnik, R. Niedermeier, C. Schubert, and P. Zschoche
  (Siehe online unter https://doi.org/10.4230/LIPIcs.ISAAC.2020.43)
• On approximate data reduction for the rural postman problem: Theory and experiments. Networks, 76(4):485–508, 2020
  R. van Bevern, T. Fluschnik, and O. Y. Tsidulko
  (Siehe online unter https://doi.org/10.1002/net.21985)
• Parameterized algorithms and data reduction for the short secluded s-t-path problem. Networks, 75(1):34–63, 2020
  R. van Bevern, T. Fluschnik, and O. Y. Tsidulko
  (Siehe online unter https://doi.org/10.1002/net.21904)
• A multistage view on 2-satisfiability. In Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC’21), volume 12701 of LNCS, pages 231–244. Springer, 2021
  T. Fluschnik
  (Siehe online unter https://doi.org/10.1007/978-3-030-75242-2_16)
• Polynomial Turing kernels for clique with optimal number of queries. 2021
  T. Fluschnik, K. Heeger, and D. Hermelin
  (Siehe online unter https://doi.org/10.48550/arXiv.2110.03279)