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$ | $2 k^2 + k$ | 36, deterministic algorithm |
| Undirected Feedback Vertex Set | $2.7^k$ | $2 k^2 + k$ | 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$ | $0.5k^2+O(k)$ | 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
Yoichi Iwata: Linear-Time Kernelization for Feedback Vertex Set. ICALP 2017: 68:1-68:14
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.
Torben Hagerup: Kernels for edge dominating set: Simpler or smaller. MFCS 2012.
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.