zbMATH — the first resource for mathematics

Streaming kernelization. (English) Zbl 1426.68120
Csuhaj-Varjú, Erzsébet (ed.) et al., Mathematical foundations of computer science 2014. 39th international symposium, MFCS 2014, Budapest, Hungary, August 25–29, 2014. Proceedings, Part II. Berlin: Springer. Lect. Notes Comput. Sci. 8635, 275-286 (2014).
Summary: Kernelization is a formalization of preprocessing for combinatorially hard problems. We modify the standard definition for kernelization, which allows any polynomial-time algorithm for the preprocessing, by requiring instead that the preprocessing runs in a streaming setting and uses \(\mathcal{O}(\mathrm{poly}(k)\log|x|)\) bits of memory on instances \((x,k)\). We obtain several results in this new setting, depending on the number of passes over the input that such a streaming kernelization is allowed to make. Edge Dominating Set turns out as an interesting example because it has no single-pass kernelization but two passes over the input suffice to match the bounds of the best standard kernelization.
For the entire collection see [Zbl 1294.68015].

68Q25 Analysis of algorithms and problem complexity
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W27 Online algorithms; streaming algorithms
Full Text: DOI