zbMATH — the first resource for mathematics

A shortcut to (sun)flowers: kernels in logarithmic space or linear time. (English) Zbl 06482817
Italiano, F. (ed.) et al., Mathematical foundations of computer science 2015. 40th international symposium, MFCS 2015, Milan, Italy, August 24–28, 2015. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-48053-3/pbk; 978-3-662-48054-0/ebook). Lecture Notes in Computer Science 9235, 299-310 (2015).
Summary: We investigate whether kernelization results can be obtained if we restrict kernelization algorithms to run in logarithmic space. This restriction for kernelization is motivated by the question of what results are attainable for preprocessing via simple and/or local reduction rules. We find kernelizations for \(d\)-hitting set\((k)\), \(d\)-set packing\((k)\), edge dominating set\((k)\), and a number of hitting and packing problems in graphs, each running in logspace. Additionally, we return to the question of linear-time kernelization. For \(d\)-hitting set\((k)\) a linear-time kernel was given by van Bevern [Algorithmica (2014)]. We give a simpler procedure and save a large constant factor in the size bound. Furthermore, we show that we can obtain a linear-time kernel for \(d\)-set packing\((k)\).
For the entire collection see [Zbl 1318.68024].

68Qxx Theory of computing
Full Text: DOI