Data reduction in parameterized algorithmics: New models and methods

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

• Final Report Year: 2018

Final Report Abstract

Im Rahmen des DAMM-Projekts konnten wir das Verständnis von Datenreduktion in der parametrisierten Algorithmik vertiefen. Wir mussten dabei in unserer Forschung häufig feststellen, dass viele Probleme keine polynomiellen Problemkerne erlauben, auch dann nicht, wenn die Eingabe des Problems eingeschränkt wird (z.B. planare Eingabegraphen) oder Parameterkombinationen betrachtet werden. Nachstehend stellen wir stichpunktartig einige Hauptergebnisse im Rahmen von DAMM dar: • Mit der von uns als Win-Win-Kernelisierung bezeichneten Methode beantworteten wir nicht nur eine aus der Literatur bekannte Frage, sondern zeigten auch auf, dass bei der Entwicklung polynomieller Problemkerne die Suche nach polynomzeitlösbaren Spezialfällen des Problems hilfreich ist. • Mit der von uns entwickelten Graphenfamilie der T-Fraktale konnten wir eine (andere) prominente offene Frage in der Literatur beantworten [A4] (Nichtexistenz eines polynomiellen Problemkerns). Wir zeigten auch, dass T-Fraktale als Werkzeug auch für andere Probleme, sowie für ungerichtete, gerichtete, und/oder planare Eingabegraphen ihre Anwendung finden. Ferner wurden die T-Fraktale auf Knotenlöschungsprobleme in planaren Graphen angepasst und für ein temporales Graphenproblem eingesetzt. • Im Rahmen des Projekts studierten wir sogenannte „Secluded“-Graphprobleme sowie das Problem, viele Zwei-Terminal-Pfade mit wenig gemeinsam genutzten Kanten zu finden. In beiden Projekten wurden zahlreiche Probleme(-varianten) auf Möglichkeiten für effiziente Datenreduktion untersucht und mehrere Publikationen erzielt, auf denen Folgearbeiten aus anderen Arbeitsgruppen aufbauten. • Im Rahmen von DAMM folgten wir dem Trend polynomzeitlösbare Probleme vom Standpunkt der parametrisierten Algorithmik aus zu studieren. In Kooperation mit dem Projekt FPTinP lag der Fokus der DAMM-Mitarbeiter auf (untere Schranken für) Kernelisierung und Varianten der Kernelisierung. Drei Projekte mit unterschiedlichen Ausrichtungen (Enumerative sowie klassische Kernelisierung, und konzeptionelle Arbeit an unteren Schranken für Kernelisierung) resultierten hierbei in Publikationen. Die konzeptionellen Beiträge finden sich dabei im Kontext strikter Kernelisierung und sogenannter Diminisher wieder. Abschließend bemerken wir, dass nicht alle Ziele aus dem Antrag erreicht wurden. Implementationen ausgewählter Datenreduktionen wurden bislang nur in Ansätzen verfolgt und erwiesen sich bisher nur partiell als vielversprechend. Zum anderen war die Entwicklung polynomieller Turing-Kernelisierung häufig nicht erfolgreich. Dies, sowie die Tatsache, dass in der Literatur wenig adaptive Turing-Kernelisierungen bekannt sind, deuten darauf hin, dass das Entwickeln solcher wohl deutlich schwieriger ist als zu Projektbeginn gehofft.

Publications

• The parameterized complexity of the minimum shared edges problem. In Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2015), volume 45 of LIPIcs, pages 448–462. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015
  T. Fluschnik, S. Kratsch, R. Niedermeier, and M. Sorge
  
• Exploiting hidden structure in selecting dimensions that distinguish vectors. Journal of Computer and System Sciences, 82(3):521– 535, 2016
  V. Froese, R. Bevern, R. Niedermeier, and M. Sorge
  
• Finding secluded places of special interest in graphs. In Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), volume 63 of LIPIcs, pages 5:1–5:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016
  R. Bevern, T. Fluschnik, G. B. Mertzios, H. Molter, M. Sorge, and O. Suchý
  
• Win-win kernelization for degree sequence completion problems. Journal of Computer and System Sciences, 82(6):1100–1111, 2016
  V. Froese, A. Nichterlein, and R. Niedermeier
  
• Parameterized aspects of triangle enumeration. In Proceedings of the 21st International Symposium on Fundamentals of Computation Theory (FCT 2017), volume 10472 of Lecture Notes in Computer Science, pages 96–110. Springer, 2017. Best Student Paper Award
  M. Bentert, T. Fluschnik, A. Nichterlein, and R. Niedermeier
  
• When can graph hyperbolicity be computed in linear time? Algorithmica, 2018. Proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS 2017)
  T. Fluschnik, C. Komusiewicz, G. B. Mertzios, A. Nichterlein, R. Niedermeier, and N. Talmon
  
• Diminishable parameterized problems and strict polynomial kernelization. In Proceedings of the 14th International Conference on Computability in Europe (CiE 2018), volume 10936 of Lecture Notes in Computer Science, pages 161–171. Springer, 2018
  H. Fernau, T. Fluschnik, D. Hermelin, A. Krebs, H. Molter, and R. Niedermeier
  
• Fractals for kernelization lower bounds. SIAM Journal on Discrete Mathematics, 32(1):656–681, 2018
  T. Fluschnik, D. Hermelin, A. Nichterlein, and R. Niedermeier
  
• Kernelization lower bounds for finding constant-size subgraphs. In Proceedings of the 14th International Conference on Computability in Europe (CiE 2018), volume 10936 of Lecture Notes in Computer Science, pages 183–193. Springer, 2018
  T. Fluschnik, G. B. Mertzios, and A. Nichterlein