Trade-offs in Parameterized Data Reduction

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

• Final Report Year: 2021

Final Report Abstract

The various insights we achieved demonstrate that there are still many important and prospective facets of research on kernelization. We have seen the (also practical) power of approximate kernelizations, the subtlety of dealing with weighted problems (indeed, weighted problems are pretty frequent in real-world applications), the promises of partial kernelization, the strength and limitations of Turing kernels, and the important role of the parameter “lifetime” in the context of kernelizing problems on temporal graphs. Nowadays, the search for (polynomial-time) data reduction rules is a well-accepted challenge when algorithmically attacking NP-hard problems—both from a theoretical as well as a practical point of view. Our project contributed to further exploring and extending the foundations of kerneliza- tion. As we saw, there are still many research avenues for future work. We believe that our work paved the way and identified some of these.

Publications

• 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
  (See online at 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
  (See online at https://doi.org/10.48550/arXiv.1910.00277)
• Multistage committee election. 2020
  R. Bredereck, T. Fluschnik, and A. Kaczmarczyk
  (See online at 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
  (See online at 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
  (See online at 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
  (See online at 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
  (See online at 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
  (See online at https://doi.org/10.48550/arXiv.2110.03279)