A shortcut to (sun)flowers: kernels in logarithmic space or linear time

DOI10.1007/978-3-662-48054-0_25MaRDI QIDQ2946401zbMATH OpenOpenAlexFDO

Authors Stefan Fafianie, Stefan Kratsch

Publication date 16 September 2015

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

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

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.

Recommendations

• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• A kernelization algorithm for \(d\)-hitting set
• Kernelization Algorithms for d-Hitting Set Problems
• Towards optimal and expressive kernelization for \(d\)-hitting set
• Towards optimal and expressive kernelization for \(d\)-hitting set

Cites work

• A shortcut to (sun)flowers: kernels in logarithmic space or linear time
• Advice classes of parametrized tractability
• An efficient fixed-parameter algorithm for 3-hitting set
• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Extremal combinatorics. With applications in computer science
• Intersection Theorems for Systems of Sets
• Kernelization of packing problems
• Parametrized complexity theory.
• Recent developments in kernelization: a survey
• Top-down lower bounds for depth-three circuits
• Towards optimal and expressive kernelization for \(d\)-hitting set

Cited in

(11)

• scientific article; zbMATH DE number 7559382 (Why is no real title available?)
• Faster FPT algorithm for 5-path vertex cover
• A shortcut to (sun)flowers: kernels in logarithmic space or linear time
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
• Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space
• Approximation in (Poly-) Logarithmic Space
• Space-efficient graph kernelizations
• Dynamic kernels for hitting sets and set packing
• Approximation in (poly-) logarithmic space
• On kernels for \(d\)-path vertex cover
• Fixed-parameter algorithms for DAG partitioning

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)