On Problems without Polynomial Kernels (Extended Abstract)
From MaRDI portal
Recommendations
Cited in
(52)- On problems without polynomial kernels
- Minimum leaf out-branching and related problems
- Extremal kernelization: a commemorative paper
- Kernelization lower bounds for finding constant-size subgraphs
- Betweenness parameterized above tight lower bound
- On some FPT problems without polynomial Turing compressions
- A completeness theory for polynomial (Turing) kernelization
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- A linear kernel for the complementary maximal strip recovery problem
- Finding a forest in a tree
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
- Clique cover and graph separation: new incompressibility results
- FPT is characterized by useful obstruction sets
- A completeness theory for polynomial (Turing) kernelization
- Kernel bounds for path and cycle problems
- Kernel bounds for structural parameterizations of pathwidth
- The birth and early years of parameterized complexity
- A basic parameterized complexity primer
- Lower bounds for kernelization
- Surfing with Rod
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
- Parameterized complexity of vertex deletion into perfect graph classes
- (Meta) kernelization
- Kernels: Annotated, Proper and Induced
- Lower bounds for kernelizations and other preprocessing procedures
- A Problem Kernelization for Graph Packing
- Incompressibility through Colors and IDs
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- 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
- Kernel bounds for path and cycle problems
- The kernelization complexity of connected domination in graphs with (no) small cycles
- Kernelization lower bounds through colors and IDs
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- Lower bounds for kernelizations and other preprocessing procedures
- Polynomial kernelizations for \(\text{MIN} \text{F}^+ \Pi_1\) and \(\text{MAX NP}\)
- On the small cycle transversal of planar graphs
- Polynomial kernels for 3-leaf power graph modification problems
- What Is Known About Vertex Cover Kernelization?
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Polynomial Turing compressions for some graph problems parameterized by modular-width
- Polynomial Turing compressions for some graph problems parameterized by modular-width
- FPT algorithms for connected feedback vertex set
- An improved kernelization algorithm for \(r\)-set packing
- FPT algorithms and kernels for the directed k-leaf problem
- A cubic kernel for feedback vertex set and loop cutset
- Linear kernelizations for restricted 3-Hitting Set problems
This page was built for publication: On Problems without Polynomial Kernels (Extended Abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3521947)
