Efficient preprocessing for hard problems: New techniques and tight models for data reduction

• Applicant: Professor Dr. Stefan Kratsch
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 225019562

• Final Report Year: 2022

Final Report Abstract

Ausgehend vom Begriff der polynomiellen Kernelisierung als Modell für effiziente Vorverarbeitung für schwere Probleme wurden in PREMOD eine Vielzahl von restriktiveren bzw. allgemeineren Modellen sowie zugehörige Techniken für obere und untere Schranken untersucht. Motiviert durch sowohl praktische als auch theoretische Überlegungen und Fragestellungen konnte so ein substanzieller Beitrag zu den Grundlagen effizienter Vorverarbeitung geleistet werden. An neuen Modellen sind insbesondere die ersten Kernelisierungen mit lediglich logarithmischem Speicher bzw. in Form von Streamingalgorithmen zu erwähnen. Auch wurde mit “preprocessing under uncertainty” eine neuartige Fragestellung zur Vorverarbeitung für effizient lösbare Probleme eingeführt und untersucht. Motiviert durch eine Frage von Lokshtanov et al. zu approximativer Kernelisierung wurden im Projekt die ersten nicht-trivialen approximativen Turingkernelisierungen entwickelt. Als weitere neue Technik sei auch die untere Schranke für Vorverarbeitung des Point Line Cover Problems erwähnt, bei der die volle Stärke der “oracle communication protocols” von Dell und van Melkebeek eingesetzt werden konnte. Des Weiteren wurden viele neue Resultate zu aktuellen Fragestellungen im Bereich Kernelisierung gewonnen. Darunter eine Vielzahl an Resultaten zu bestmöglichen Parametern für Vertex Cover, die eine polynomielle Kernelisierung erlauben, sowie deren Charakterisierung. Ebenso neue Resultate zu matroid-basierten Kernelisierungen, aufbauend auf Arbeiten von Kratsch und Wahlström. Nicht zuletzt konnten viele Erkenntnisse zur Kernelisierbarkeit von Problemen auf ganzzahligen linearen Programmen gewonnen werden.

Publications

• On Polynomial Kernels for Integer Linear Programs: Covering, Packing and Feasibility. ESA 2013: 647-658
  Stefan Kratsch
  
• Streaming Kernelization. MFCS (2) 2014: 275-286
  Stefan Fafianie, Stefan Kratsch
  
• A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity. ESA 2015: 779-791
  Bart M. P. Jansen, Stefan Kratsch
  
• A Randomized Polynomial Kernel for Subset Feedback Vertex Set. Theory Comput. Syst. 62(1): 63-92 (2018)
  Eva-Maria C. Hols, Stefan Kratsch
  
• Point Line Cover: The Easy Kernel is Essentially Tight. ACM Trans. Algorithms 12(3): 40:1-40:16 (2016)
  Stefan Kratsch, Geevarghese Philip, Saurabh Ray
  
• Preprocessing Under Uncertainty. STACS 2016: 33:1-33:13
  Stefan Fafianie, Stefan Kratsch, Vuong Anh Quyen
  
• A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. SIAM J. Discret. Math. 32(3): 1806-1839 (2018)
  Stefan Kratsch
  
• On Kernelization for Edge Dominating Set under Structural Parameters. STACS 2019: 36:1-36:18
  Eva-Maria C. Hols, Stefan Kratsch
  
• Approximate Turing Kernelization for Problems Parameterized by Treewidth. ESA 2020: 60:1-60:23
  Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
  
• Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. STACS 2020: 36:1-36:14
  Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse