Greedy localization, iterative compression, and modeled crown reductions: new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover

F Dehne, M. Fellows, F. Rosamond, P. Shaw

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

Abstract

The two objectives of this paper are: (1) to articulate three new general techniques for designing FPT algorithms, and (2) to apply these to obtain new FPT algorithms for SET SPLITTING and VERTEX COVER. In the case of SET SPLITTING, we improve the best previous O*(72k) FPT algorithm due to Dehne, Fellows and Rosamond [DFR03], to O*(8k) by an approach based on greedy localization in conjunction with modeled crown reduction. In the case of VERTEX COVER, we describe a new approach to 2k kernelization based on iterative compression and crown reduction, providing a potentially useful alternative to the Nemhauser-Trotter 2k kernelization. © Springer-Verlag 2004.
Original languageEnglish
Title of host publicationParameterized and Exact Computation
Subtitle of host publicationFirst International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings
EditorsRod Downey, Michael Fellows, Frank Dehne
PublisherSpringer
Pages271-280
Number of pages10
ISBN (Electronic)978-3-540-28639-4
ISBN (Print)978-3-540-23071-7
DOIs
Publication statusPublished - 2004
Externally publishedYes

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3162
ISSN (Print)0302-9743

Cite this

Dehne, F., Fellows, M., Rosamond, F., & Shaw, P. (2004). Greedy localization, iterative compression, and modeled crown reductions: new fpt techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover. In R. Downey, M. Fellows, & F. Dehne (Eds.), Parameterized and Exact Computation: First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings (pp. 271-280). (Lecture Notes in Computer Science ; Vol. 3162). Springer. https://doi.org/10.1007/978-3-540-28639-4_24