On Problems without Polynomial Kernels (Extended Abstract)

DOI10.1007/978-3-540-70575-8_46zbMath1153.68554OpenAlexW2169262928WikidataQ57359900 ScholiaQ57359900MaRDI QIDQ3521947

Michael R. Fellows, Danny Hermelin, Rodney G. Downey, Hans L. Bodlaender

Publication date: 28 August 2008

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70575-8_46

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items

Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds, The Birth and Early Years of Parameterized Complexity, FPT algorithms and kernels for the directed \(k\)-leaf problem, A Basic Parameterized Complexity Primer, Polynomial kernels for 3-leaf power graph modification problems, Infeasibility of instance compression and succinct PCPs for NP, What Is Known About Vertex Cover Kernelization?, Surfing with Rod, Betweenness parameterized above tight lower bound, The kernelization complexity of connected domination in graphs with (no) small cycles, A linear kernel for the complementary maximal strip recovery problem, Lower Bounds for Kernelizations and Other Preprocessing Procedures, FPT algorithms for connected feedback vertex set, Lower bounds for kernelizations and other preprocessing procedures, A cubic kernel for feedback vertex set and loop cutset, On the small cycle transversal of planar graphs, A Problem Kernelization for Graph Packing, Linear kernelizations for restricted 3-Hitting Set problems, Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs, On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems, Finding a Forest in a Tree, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, An improved kernelization algorithm for \(r\)-set packing, Minimum leaf out-branching and related problems, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, Kernelization: New Upper and Lower Bound Techniques, On Finding Directed Trees with Many Leaves, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms, Two Edge Modification Problems without Polynomial Kernels