Table of FPT races

The results gradually keep improving. Please add your latest to the table.

NEWS: Edge clique cover does not have polynomial kernel (see 35). It was open for some time.
Very nice paper to read, so enjoy! — Saket

Problem f(k) vertices in kernel Reference/Comments
Vertex Cover $1.2738^{k}$ $2k$ 1
Connected Vertex Cover $2^{k}$ no $k^{O(1)}$ 26, randomized algorithm
Multiway Cut $2^k$ not known 21, 38: $O(k^{s+1})$-vertex kernel with $s$ terminals
Directed Multiway Cut $2^{O(k^3)}$ no $k^{O(1)}$ 34
Almost-2-SAT (VC-PM) $2.3146^k$ $O(k^6)$ 37, 38, randomized kernel
Multicut $2^{O(k^3)}$ no $k^{O(1)}$ 22, 35
Pathwidth One Deletion Set $4.65^k$ $O(k^2)$ 28
Undirected Feedback Vertex Set $3.619^k$ $4 k^2$ 36, deterministic algorithm
Undirected Feedback Vertex Set $3^k$ $4 k^2$ 23, randomized algorithm
Subset Feedback Vertex Set $4^k$ not known 39
Directed Feedback Vertex Set $4^k k!$ not known 27
Odd Cycle Transversal $2.3146^k$ $O(k^{4.5})$ 37, 38, randomized kernel; kernel is for signed graph generalization
Edge Bipartization $2^k$ $\tilde O(k^3)$ 25, 38, randomized kernel; kernel is for signed graph generalization
Planar DS $2^{11.98 \sqrt{k}}$ $67k$ 3
1-Sided Crossing Min $2^{O(\sqrt{ k}\log k)}$ $O(k^2)$ 4
Max Leaf $3.72^{k}$ $3.75k$ 5
Directed Max Leaf $3.72^{k}$ $O(k^2)$ 6
Set Splitting $1.8213^{k}$ $k$ 7
Nonblocker $2.5154^{k}$ $5k/3$ 8
Edge Dominating Set $2.3147^k$ $2k^2+2k$ 10
k-Path $2.851^{k}$ no $k^{O(1)}$ 40, deterministic algorithm
k-Path $1.66^{k}$ no $k^{O(1)}$ 11b, randomized algorithm
Convex Recolouring $4^k$ $O(k^2)$ 12
VC-max degree 3 $1.1616^k$ 13
Clique Cover $2^{2^k}$ $2^k$ 14
Clique Partition $2^{k^2}$ $k^2$ 15
Cluster Editing $1.62^k$ $2k$ 16, weighted and unweighted
Steiner Tree $2^k$ no $k^{O(1)}$ 17
3-Hitting Set $2.076^k$ $O(k^2)$ 18
Interval Completion $O(k^{2k}n^3 )$ not known 19
Minimum Fill-In $2^{O(\sqrt{k}\log k )}$ $2k^2+2k$ 20
Contraction to Paths $2^{k+ o(k) }$ $5k+3$ 30
Contraction to Trees $4^k/4.98^{k}$ no $k^{O(1)}$ 30, randomized/deterministic algorithm
Planar Disjoint Path $2^{O(2^k)}$ not known 31
Max Internal Spanning Tree $8^{k}$ $3k$ 32
Directed Max Internal Spanning Tree $16^{k+ \log k}$ $O(k^2)$ 33

1) Jianer Chen, Iyad A. Kanj, Ge Xia: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40-42): 3736-3756 (2010)
2) Yixin Cao, Jianer Chen, Yang Liu: On Feedback Vertex Set New Measure and New Structures. SWAT 2010: 93-104
Stéphan Thomassé: A $4k^2$ kernel for feedback vertex set. ACM Transactions on Algorithms 6(2): (2010)
3) Frederic Dorn: Dynamic Programming and Fast Matrix Multiplication. ESA 2006: 280-291
Jianer Chen, Henning Fernau, Iyad A. Kanj, Ge Xia: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on
Kernel Size. SIAM J. Comput. 37(4): 1077-1106 (2007)
4) Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, Saket Saurabh: Ranking and Drawing
in Subexponential Time. IWOCA 2010: 337-348
Vida Dujmovic, Henning Fernau, Michael Kaufmann: Fixed parameter algorithms for one-sided crossing minimization revisited. J. Discrete Algorithms 6(2): 313-323 (2008)
5) Jean Daligault, Gregory Gutin, Eun Jung Kim, Anders Yeo: FPT algorithms and kernels for the Directed k-Leaf problem.
J. Comput. Syst. Sci. 76(2): 144-152 (2010)
V. Estivill-Castro, M. Fellows, M. Langston and F. Rosamond. Fixed-Parameter Tractability is Polynomial-Time Extremal Structure
Theory I: The Case of Max Leaf. ACiD, (2004).
6) Jean Daligault, Gregory Gutin, Eun Jung Kim, Anders Yeo: FPT algorithms and kernels for the Directed k-Leaf problem.
J. Comput. Syst. Sci. 76(2): 144-152 (2010)
Jean Daligault, Stéphan Thomassé: On Finding Directed Trees with Many Leaves. IWPEC 2009: 86-97
7) Jesper Nederlof, Johan M. M. van Rooij: Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting. IPEC 2010: 204-215
Daniel Lokshtanov, Saket Saurabh: Even Faster Algorithm for Set Splitting! IWPEC 2009: 288-299
8) Frank K. H. A. Dehne, Michael R. Fellows, Henning Fernau, Elena Prieto, Frances A. Rosamond: NONBLOCKER: Parameterized Algorithmics for minimum dominating set. SOFSEM 2006: 237-245
10) Mingyu Xiao, Ton Kloks, Sheung-Hung Poon: New parameterized algorithms for edge dominating set CoRR abs/1104.4160: (2011). To appear in MFCS 2011.
11a) Jianer Chen, Joachim Kneis, Songjian Lu, Daniel Mölle, Stefan Richter, Peter Rossmanith, Sing-Hoi Sze, and Fenghui Zhang: Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms. SIAM J. Comput. 38: 2526-2547 (2009)
Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8): 423-434 (2009)
11b) Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto: Narrow sieves for parameterized paths and packings CoRR abs/1007.1161: (2010)
Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8): 423-434 (2009)
12) Oriana Ponta, Falk Hüffner, Rolf Niedermeier: Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems. TAMC 2008: 490-501
Hans L. Bodlaender, Michael R. Fellows, Michael A. Langston, Mark A. Ragan, Frances A. Rosamond, Mark Weyer: Quadratic Kernelization for Convex Recoloring of Trees. COCOON 2007: 86-96
13) Mingyu Xiao: A Note on Vertex Cover in Graphs with Maximum Degree 3. COCOON 2010: 150-159
14) Jens Gramm, Jiong Guo, Falk Hüffner, Rolf Niedermeier: Data reduction and exact algorithms for clique cover. ACM Journal of Experimental Algorithmics 13: (2008)
15) Egbert Mujuni, Frances A. Rosamond: Parameterized Complexity of the Clique Partition Problem. CATS 2008: 75-78
16) Sebastian Böcker: A Golden Ratio Parameterized Algorithm for Cluster Editing. To appear in IWOCA 2011.
Yixin Cao, Jianer Chen: Cluster editing: kernelization based on edge-cuts. IPEC 2010: 60-71
17) Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto: Fourier meets möbius: fast subset convolution. STOC 2007: 67-74
Jesper Nederlof: Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems. ICALP (1) 2009: 713-725
Michael Dom, Daniel Lokshtanov, Saket Saurabh: Incompressibility through Colors and IDs. ICALP (1) 2009: 378-389
18) M. Wahlstr\"om. Algorithms, Measures and Upper Bounds for Satisfiability and Related Problems.PhD Thesis, Department of Computer and Information Science, Link\"opings universitet, Sweden, 2007.
Faisal N. Abu-Khzam: A kernelization algorithm for d-Hitting Set. J. Comput. Syst. Sci. 76(7): 524-531 (2010)
19) Yngve Villanger, Pinar Heggernes, Christophe Paul, Jan Arne Telle: Interval Completion Is Fixed Parameter Tractable. SIAM J. Comput. 38(5): 2007-2020 (2009)
20) Fedor V. Fomin, Yngve Villanger: Subexponential Parameterized Algorithm for Minimum Fill-in CoRR abs/1104.2230: (2011)
Assaf Natanzon, Ron Shamir, Roded Sharan: A Polynomial Approximation Algorithm for the Minimum Fill-In Problem. SIAM J. Comput. 30(4): 1067-1079 (2000)
21) Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk: On Multiway Cut parameterized above lower bounds. To appear in IPEC 2011.
22) Dániel Marx, Igor Razgon: Fixed-parameter tractability of multicut parameterized by the size of the cutset. STOC 2011: 469-478
23) Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk: Solving connectivity problems parameterized by treewidth in single exponential time CoRR abs/1103.0534: (2011). To appear in FOCS 2011.
Stéphan Thomassé: A $4k^2$ kernel for feedback vertex set. ACM Transactions on Algorithms 6(2): (2010)
24) Bruce A. Reed, Kaleigh Smith, Adrian Vetta: Finding odd cycle transversals. Oper. Res. Lett. 32(4): 299-301 (2004)
Stefan Kratsch, Magnus Wahlström: Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal.
http://arxiv.org/abs/1107.3068
25) Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, Sebastian Wernicke: Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization. J. Comput. Syst. Sci. 72(8): 1386-1396 (2006)
Stefan Kratsch, Magnus Wahlström: Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal.
http://arxiv.org/abs/1107.3068
26) Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, Jakub Onufry Wojtaszczyk: Solving connectivity problems parameterized by treewidth in single exponential time CoRR abs/1103.0534: (2011). To appear in FOCS 2011.
Michael Dom, Daniel Lokshtanov, Saket Saurabh: Incompressibility through Colors and IDs. ICALP (1) 2009: 378-389
27) Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5): (2008)
28) Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion. IPEC 2010: 95-106
29) Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, Jakub Onufry Wojtaszczyk: Subset Feedback Vertex Set Is Fixed-Parameter Tractable. ICALP (1) 2011: 449-461
30) Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, Daniel Lokshtanov, Christophe Paul: Contracting Graphs to Paths and Trees CoRR abs/1104.3677: (2011). To appear in IPEC 2011.
31) Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos: Tight Bounds for Linkages in Planar Graphs. ICALP (1) 2011: 110-121
32) Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Stéphan Thomassé: A Linear Vertex Kernel for Maximum Internal Spanning Tree. ISAAC 2009: 275-282
33) Fedor V. Fomin, Daniel Lokshtanov, Fabrizio Grandoni, Saket Saurabh: Sharp Separation and Applications to Exact and Parameterized Algorithms. LATIN 2010: 72-83
Gregory Gutin, Igor Razgon, Eun Jung Kim: Minimum leaf out-branching and related problems. Theor. Comput. Sci. 410(45): 4571-4579 (2009)
34) Rajesh Chitnis, MohammadTaghi Hajiaghayi, Dániel Marx: Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset, CoRR abs/1110.0259: (2011). To appear in SODA 2012.
35) Marek Cygan, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, Magnus Wahlström}, Clique cover and graph separation: New incompressibility results, CoRR abs/1111.0570: (2011)
36) Tomasz Kociumaka, Marcin Pilipczuk. Faster deterministic Feedback Vertex Set. Information Processing Letters.
37) Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh: Faster Parameterized Algorithms Using Linear Programming. ACM Transactions on Algorithms (TALG) 11(2):15:1-15:31 (2014)
38) Stefan Kratsch, Magnus Wahlström: Representative Sets and Irrelevant Vertices: New Tools for Kernelization. FOCS 2012:450-459
39) Yoichi Iwata, Magnus Wahlström, Yuichi Yoshida: Half-integrality, LP-branching and FPT Algorithms, CoRR abs/1310.2841 (2014). Extended version of (Wahlström, SODA 2014).
40) Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh: Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms. SODA 2014:142-151

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License