Optimal-size problem kernels for d-Hitting Set in linear time and space

The known linear-time kernelizations for d-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size O(kd) for d-Hitting Set are computab...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2020-11, Vol.163, p.105998, Article 105998
Main Authors: van Bevern, René, Smirnov, Pavel V.
Format: Article
Language:English
Subjects:
Combinatorial problems
Data reduction
Kernelization
NP-hard problem
Parameterized complexity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The known linear-time kernelizations for d-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size O(kd) for d-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for d-Hitting Set to each other and to a classical data reduction algorithm due to Weihe. •Linear-time and space kernelizations for d-Hitting Set.•Experimental comparison to well-known data reduction algorithm of Weihe.•For low parameter values, kernelization is superior.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2020.105998