Streaming kernelization

DOI10.1007/978-3-662-44465-8_24MaRDI QIDQ2922615zbMATH OpenOpenAlexFDO

Authors Stefan Fafianie, Stefan Kratsch

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.1356

Mathematics Subject Classification ID

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

Abstract: 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 $mathcalO(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.

Recommendations

• Recent developments in kernelization: a survey
• Kernelization -- preprocessing with a guarantee
• Kernels for edge dominating set: simpler or smaller
• Lower bounds on kernelization
• Lossy kernelization

Cited in

(20)

• Optimal-size problem kernels for d-Hitting Set in linear time and space
• Linear-time parameterized algorithms with limited local resources
• Multistage graph problems on a global budget
• Dynamic graph stream algorithms in \(o(n)\) space
• Fixed parameter tractability of graph deletion problems over data streams
• Nearly time-optimal kernelization algorithms for the line-cover problem with big data
• A linear-time kernelization for the rooted k-leaf outbranching problem
• Space-efficient vertex separators for treewidth
• Streaming deletion problems parameterized by vertex cover
• Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
• Parameterized complexity of streaming diameter and connectivity problems
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Space limited linear-time graph algorithms on big data
• Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
• Parameterized quantum query algorithms for graph problems
• An incremental kernel density estimator for data stream computation
• Streaming Embeddings with Slack
• Space limited graph algorithms on big data
• Parameterized complexity of streaming diameter and connectivity problems
• Streaming deletion problems Parameterized by vertex cover

This page was built for publication: Streaming kernelization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922615)