Smaller kernels for hitting set problems of constant arity

Naomi Nishimura; Prabhakar Ragde; Dimitrios M. Thilikos

doi:10.1007/978-3-540-28639-4_11

Smaller kernels for hitting set problems of constant arity

Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

We demonstrate a kernel of size O(k²) for 3-HITTING SET (HITTING SET when all subsets in the collection to be hit are of size at most three), giving a partial answer to an open question of Niedermeier by improving on the O(k³) kernel of Niedermeier and Rossmanith. Our technique uses the Nemhauser-Trotter linear-size kernel for VERTEX COVER, and generalizes to demonstrating a kernel of size O(k^r-1) for r-HITTING SET (for fixed r).

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Rod Downey, Michael Fellows, Frank Dehne
Publisher	Springer Verlag
Pages	121-126
Number of pages	6
ISBN (Print)	9783540230717
DOIs	https://doi.org/10.1007/978-3-540-28639-4_11
State	Published - 2004

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3162
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

Fixed parameter algorithms
Hitting set
Kernels

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-28639-4_11

Cite this

Nishimura, N., Ragde, P., & Thilikos, D. M. (2004). Smaller kernels for hitting set problems of constant arity. In R. Downey, M. Fellows, & F. Dehne (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 121-126). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3162). Springer Verlag. https://doi.org/10.1007/978-3-540-28639-4_11

Smaller kernels for hitting set problems of constant arity. / Nishimura, Naomi; Ragde, Prabhakar; Thilikos, Dimitrios M.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Rod Downey; Michael Fellows; Frank Dehne. Springer Verlag, 2004. p. 121-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3162).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Nishimura, N, Ragde, P & Thilikos, DM 2004, Smaller kernels for hitting set problems of constant arity. in R Downey, M Fellows & F Dehne (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3162, Springer Verlag, pp. 121-126. https://doi.org/10.1007/978-3-540-28639-4_11

Nishimura N, Ragde P, Thilikos DM. Smaller kernels for hitting set problems of constant arity. In Downey R, Fellows M, Dehne F, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2004. p. 121-126. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-28639-4_11

Nishimura, Naomi ; Ragde, Prabhakar ; Thilikos, Dimitrios M. / Smaller kernels for hitting set problems of constant arity. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Rod Downey ; Michael Fellows ; Frank Dehne. Springer Verlag, 2004. pp. 121-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{05cb64bac22c457aaec4977fb9a75f71,

title = "Smaller kernels for hitting set problems of constant arity",

abstract = "We demonstrate a kernel of size O(k2) for 3-HITTING SET (HITTING SET when all subsets in the collection to be hit are of size at most three), giving a partial answer to an open question of Niedermeier by improving on the O(k3) kernel of Niedermeier and Rossmanith. Our technique uses the Nemhauser-Trotter linear-size kernel for VERTEX COVER, and generalizes to demonstrating a kernel of size O(kr-1) for r-HITTING SET (for fixed r).",

keywords = "Fixed parameter algorithms, Hitting set, Kernels",

author = "Naomi Nishimura and Prabhakar Ragde and Thilikos, {Dimitrios M.}",

year = "2004",

doi = "10.1007/978-3-540-28639-4_11",

language = "English (US)",

isbn = "9783540230717",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "121--126",

editor = "Rod Downey and Michael Fellows and Frank Dehne",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - Smaller kernels for hitting set problems of constant arity

AU - Nishimura, Naomi

AU - Ragde, Prabhakar

AU - Thilikos, Dimitrios M.

PY - 2004

Y1 - 2004

N2 - We demonstrate a kernel of size O(k2) for 3-HITTING SET (HITTING SET when all subsets in the collection to be hit are of size at most three), giving a partial answer to an open question of Niedermeier by improving on the O(k3) kernel of Niedermeier and Rossmanith. Our technique uses the Nemhauser-Trotter linear-size kernel for VERTEX COVER, and generalizes to demonstrating a kernel of size O(kr-1) for r-HITTING SET (for fixed r).

AB - We demonstrate a kernel of size O(k2) for 3-HITTING SET (HITTING SET when all subsets in the collection to be hit are of size at most three), giving a partial answer to an open question of Niedermeier by improving on the O(k3) kernel of Niedermeier and Rossmanith. Our technique uses the Nemhauser-Trotter linear-size kernel for VERTEX COVER, and generalizes to demonstrating a kernel of size O(kr-1) for r-HITTING SET (for fixed r).

KW - Fixed parameter algorithms

KW - Hitting set

KW - Kernels

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

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

U2 - 10.1007/978-3-540-28639-4_11

DO - 10.1007/978-3-540-28639-4_11

M3 - Chapter

AN - SCOPUS:24144487577

SN - 9783540230717

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 121

EP - 126

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Downey, Rod

A2 - Fellows, Michael

A2 - Dehne, Frank

PB - Springer Verlag

ER -

Smaller kernels for hitting set problems of constant arity

Abstract

Publication series

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this