Efficient preprocessing for hard problems: New techniques and tight models for data reduction
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
(See online at https://doi.org/10.1007/978-3-642-40450-4_55) - Streaming Kernelization. MFCS (2) 2014: 275-286
Stefan Fafianie, Stefan Kratsch
(See online at https://doi.org/10.1007/978-3-662-44465-8_24) - A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity. ESA 2015: 779-791
Bart M. P. Jansen, Stefan Kratsch
(See online at https://doi.org/10.1007/978-3-662-48350-3_65) - A Randomized Polynomial Kernel for Subset Feedback Vertex Set. Theory Comput. Syst. 62(1): 63-92 (2018)
Eva-Maria C. Hols, Stefan Kratsch
(See online at https://doi.org/10.1007/s00224-017-9805-6) - 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
(See online at https://doi.org/10.1145/2832912) - Preprocessing Under Uncertainty. STACS 2016: 33:1-33:13
Stefan Fafianie, Stefan Kratsch, Vuong Anh Quyen
(See online at https://doi.org/10.4230/LIPIcs.STACS.2016.33) - A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. SIAM J. Discret. Math. 32(3): 1806-1839 (2018)
Stefan Kratsch
(See online at https://doi.org/10.1137/16M1104585) - On Kernelization for Edge Dominating Set under Structural Parameters. STACS 2019: 36:1-36:18
Eva-Maria C. Hols, Stefan Kratsch
(See online at https://doi.org/10.4230/LIPIcs.STACS.2019.36) - Approximate Turing Kernelization for Problems Parameterized by Treewidth. ESA 2020: 60:1-60:23
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
(See online at https://doi.org/10.4230/LIPIcs.ESA.2020.60) - Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. STACS 2020: 36:1-36:14
Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse
(See online at https://doi.org/10.4230/LIPIcs.STACS.2020.36)
