Kernelization dichotomies for hitting subgraphs under structural parameterizations
From MaRDI portal
Cites work
- \textsc{Planar} \(\mathcal{F}\)-\textsc{deletion}: approximation, kernelization and optimal FPT algorithms
- A kernelization algorithm for \(d\)-hitting set
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Algorithms and data structures for first-order logic with connectivity under vertex failures
- Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
- Cross-composition: a new technique for kernelization lower bounds
- Deleting, eliminating and decomposing to hereditary classes are all FPT-equivalent
- Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
- Faster parameterized algorithms for modification problems to minor-closed classes
- Fixed-parameter tractable distances to sparse graph classes
- Graph isomorphism parameterized by elimination distance to bounded degree
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Hitting forbidden subgraphs in graphs of bounded treewidth
- Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- Kernelization -- preprocessing with a guarantee
- Kernelization for feedback vertex set via elimination distance to a forest
- Kernelization Lower Bounds by Cross-Composition
- Kernelization using structural parameters on sparse graph classes
- Kernelization. Theory of parameterized preprocessing
- Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
- On polynomial kernels for structural parameterizations of odd cycle transversal
- On problems without polynomial kernels
- On the hardness of losing width
- Parameterized algorithms
- Parameterized and Exact Computation
- Parameterized complexity of computing maximum minimal blocking and hitting sets
- Parameterized complexity of elimination distance to first-order logic properties
- Parametrized complexity theory.
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Representative sets and irrelevant vertices: new tools for kernelization
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- The node-deletion problem for hereditary properties is NP-complete
- Treewidth. Computations and approximations
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Vertex cover structural parameterization revisited
- Vertex deletion parameterized by elimination distance and even less
- What Is Known About Vertex Cover Kernelization?
This page was built for publication: Kernelization dichotomies for hitting subgraphs under structural parameterizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875175)
