Theoretical and Practical Aspects of Kernelization
Final Report Abstract
Kernelization is the mathematical study of preprocessing algorithms. A kernelization algorithm essentially strips away the easy parts of a problem instance exposing the core or the kernel. It is currently a very important topic of research in parameterized complexity. Recently, strong lower bounds on the existence of polynomial kernels, the new concept of lossy kernels, and the existence of Turing kernels have renewed interest in the area. In this project the main goals were the generalization of meta kernelization results. Such results existed for several structurally sparse graph classes starting from planar graphs and reaching to H-minor free graphs. We could find new meta kernelization results first for the next more general graph class, i.e., graphs that exclude a topological minor rather than a (normal) minor. Then new kernels could be found for graphs of bounded expansion, locally bounded expansion, and nowhere dense graph classes. Such results use new structural parameters rather the solution size and we have shown that this is necessary. While on first glance this seems to be weakening the result, it turns out that in earlier results the natural parameters had the same effect (in the bidimensionalty approach the solution has to be big on a grid, for example). Along this research we had to find new algorithmic ideas as the methods of bidimensionality no longer work on these more general graph classes. An important ingredient are treedepth modulators and ultimately the protrusion replacement factory with its import finite integer index requirement. By relaxing the FII requirement to a relative condition that needs to hold only in sparse graph classes rather than in general graphs we could extend the pool of problems that can be kernelized substantially, e.g., also including the longest path problem, which cannot have a polynomial kernel even in planar graphs when parameterized by the length of the path. Several side results were either necessary to achieve efficient running times or small kernel sizes or offered themselves naturally along our main research. These include among others the now fastest algorithm to compute treedepth decompositions (needed in the protrusion replacement during kernelization) and lower space bounds on solving problems on a treedepth (or tree) decomposition.
Publications
- Kernelization using structural parameters on sparse graph classes. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 529–540, 2013
Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar
(See online at https://doi.org/10.1007/978-3-642-40450-4_45) - Linear kernels and singleexponential algorithms via protrusion decompositions. In ICALP (1), volume 7965 of Lecture Notes in Computer Science, pages 613–624. Springer, 2013
Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar
(See online at https://doi.org/10.1007/978-3-642-39206-1_52) - A faster parameterized algorithm for treedepth. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 931–942, 2014
Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar
(See online at https://doi.org/10.1007/978-3-662-43948-7_77) - Digraph width measures in parameterized algorithmics. Discrete Applied Mathematics, 168:88–107, 2014
Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, and Peter Rossmanith
(See online at https://doi.org/10.1016/j.dam.2013.10.038) - Finite integer index of pathwidth and treewidth. In Parameterized and Exact Computation - 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers, pages 258–269, 2014
Jakub Gajarský, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar
(See online at https://doi.org/10.1007/978-3-319-13524-3_22) - Kernelization and sparseness: the case of dominating set. In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 31:1–31:14, 2016
Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar
(See online at https://doi.org/10.4230/LIPIcs.STACS.2016.31) - Linear kernels and singleexponential algorithms via protrusion decompositions. ACM Trans. Algorithms, 12(2):21:1–21:41, 2016
Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar
(See online at https://doi.org/10.1145/2797140) - Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci., 84:219–242, 2017
Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar
(See online at https://doi.org/10.1016/j.jcss.2016.09.002) - Width, depth, and space: Tradeoffs between branching and dynamic programming. Algorithms, 11(7):98, 2018
Li-Hsuan Chen, Felix Reidl, Peter Rossmanith, and Fernando Sánchez Villaamil
(See online at https://doi.org/10.3390/a11070098)
