Abstract

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.

Original languageEnglish
Article number105998
Number of pages9
JournalInformation Processing Letters
Volume163
DOIs
Publication statusPublished - 1 Nov 2020

Keywords

  • Combinatorial problems
  • Data reduction
  • Kernelization
  • NP-hard problem
  • Parameterized complexity

OECD FOS+WOS

  • 1.02 COMPUTER AND INFORMATION SCIENCES

Fingerprint

Dive into the research topics of 'Optimal-size problem kernels for d-Hitting Set in linear time and space'. Together they form a unique fingerprint.

Cite this