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.460^k$ $4 k^2$ 36, deterministic algorithm
Undirected Feedback Vertex Set $2.7^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+\delta)^k$ no $k^{O(1)}$ 41, weighted, for any constant $\delta>0$
Steiner Tree $2^k$ no $k^{O(1)}$ 17, unweighted
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) Jason Li, Jesper Nederlof: Detecting Feedback Vertex Sets of Size k in $O^*(2.7^k)$ Time. CoRR abs/1906.12298 (2019)
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) Yoichi Iwata, Yusuke Kobayashi: Improved Analysis of Highest-Degree Branching for Feedback Vertex Set. CoRR abs/1905.12233 (2019)
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
41) B. Fuchs, W. Kern, D. Molle, S. Richter, P. Rossmanith and X. Wang. ‘Dynamic programming for minimum Steiner trees’. Theory of Computing Systems 41.3 (2007), pp. 493–500.

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