A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time

DOI10.1007/978-3-662-48054-0_25zbMATH Open1465.68111arXiv1504.08235OpenAlexW2248154729MaRDI QIDQ2946401

Author name not available (Why is that?)

Publication date: 16 September 2015

Published in: (Search for Journal in Brave)

Abstract: 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 kernelization 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) as well.

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

Mathematics Subject Classification ID

No records found.

This page was built for publication: A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time

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