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

René van Bevern; Pavel V. Smirnov

doi:10.1016/j.ipl.2020.105998

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

René van Bevern, Pavel V. Smirnov

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

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(k^d) 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 language	English
Article number	105998
Number of pages	9
Journal	Information Processing Letters
Volume	163
DOIs	https://doi.org/10.1016/j.ipl.2020.105998
Publication status	Published - 1 Nov 2020

Keywords

Combinatorial problems
Data reduction
Kernelization
NP-hard problem
Parameterized complexity

Access to Document

10.1016/j.ipl.2020.105998

Link to publication in Scopus

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

@article{0f43df8947d84d419ec252fe40388ad9,

title = "Optimal-size problem kernels for d-Hitting Set in linear time and space",

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.",

keywords = "Combinatorial problems, Data reduction, Kernelization, NP-hard problem, Parameterized complexity",

author = "{van Bevern}, Ren{\'e} and Smirnov, {Pavel V.}",

year = "2020",

month = nov,

day = "1",

doi = "10.1016/j.ipl.2020.105998",

language = "English",

volume = "163",

journal = "Information Processing Letters",

issn = "0020-0190",

}

TY - JOUR

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

AU - van Bevern, René

AU - Smirnov, Pavel V.

PY - 2020/11/1

Y1 - 2020/11/1

N2 - 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.

AB - 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.

KW - Combinatorial problems

KW - Data reduction

KW - Kernelization

KW - NP-hard problem

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=85087713620&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2020.105998

DO - 10.1016/j.ipl.2020.105998

M3 - Article

AN - SCOPUS:85087713620

VL - 163

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

M1 - 105998

ER -