On problems without polynomial kernels

2009/04/06 by Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows +1 · 344 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Kernel method #Kernelization #Mathematics #Parameterized complexity #Pathwidth #Polynomial #Polynomial hierarchy #Polynomial kernel #Time complexity #Treewidth

paper · pdf · doi:10.1016/j.jcss.2009.04.001

published in Journal of Computer and System Sciences 75(8), 423-434 (Elsevier BV)

openalex publication_date 2009/04/06 · crossref created 2009/04/06 · crossref issued 2009/12/01 · crossref published 2009/12/01 · crossref published-print 2009/12/01 · crossref deposited 2025/02/08 · openalex created_date 2025/10/10 · crossref indexed 2026/07/30 · openalex updated_date 2026/08/03

Citations

• Parameterized Complexity Theory
• Efficiently four-coloring planar graphs
• The importance of being biased
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A survey
• The complexity of theorem-proving procedures
• On the Structure of Polynomial Time Reducibility
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Advice classes of parameterized tractability
• A partial k-arboretum of graphs with bounded treewidth
• Polynomial-time data reduction for dominating set
• Parameterized Complexity

Cited by

• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Max-Cut Parameterized Above the Edwards-Erdős Bound
• Satisfying more than half of a system of linear equations over GF(2): A multivariate approach
• Kernelization [wikipedia]