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.
|Title of host publication||Parameterized and Exact Computation|
|Subtitle of host publication||First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings|
|Editors||Rod Downey, Michael Fellows, Frank Dehne|
|Number of pages||10|
|Publication status||Published - 2004|
|Name||Lecture Notes in Computer Science|
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