(Meta) Kernelization

DOI10.1109/FOCS.2009.46zbMath1292.68089OpenAlexW2295651994WikidataQ59567683 ScholiaQ59567683MaRDI QIDQ5171201

Eelko Penninkx, Saket Saurabh, Fedor V. Fomin, Daniel Lokshtanov, Dimitrios M. Thilikos, Hans L. Bodlaender

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.46

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (81)

On polynomial kernels for sparse integer linear programs ⋮ Characterising bounded expansion by neighbourhood complexity ⋮ On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ On the Hardness of Losing Width ⋮ Simpler Linear-Time Kernelization for Planar Dominating Set ⋮ Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ A Retrospective on (Meta) Kernelization ⋮ \((1, j)\)-set problem in graphs ⋮ Win-win kernelization for degree sequence completion problems ⋮ Uniform Kernelization Complexity of Hitting Forbidden Minors ⋮ Edge-disjoint packing of stars and cycles ⋮ A Basic Parameterized Complexity Primer ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Graph Minors and Parameterized Algorithm Design ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Editing to a Planar Graph of Given Degrees ⋮ Planar graph vertex partition for linear problem kernels ⋮ Minors in graphs of large \(\theta_r\)-girth ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ On kernelization and approximation for the vector connectivity problem ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ Parameterized and approximation algorithms for the load coloring problem ⋮ Quick but odd growth of cacti ⋮ A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Finite Integer Index of Pathwidth and Treewidth ⋮ Improved linear problem kernel for planar connected dominating set ⋮ Effective computation of immersion obstructions for unions of graph classes ⋮ Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Meta-kernelization with structural parameters ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Fractals for Kernelization Lower Bounds ⋮ On the hardness of losing width ⋮ Contracting graphs to paths and trees ⋮ Lower bounds on kernelization ⋮ Backdoor Sets for CSP. ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Kernels for feedback arc set in tournaments ⋮ Spanners in sparse graphs ⋮ Implicit branching and parameterized partial cover problems ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles ⋮ Finding disjoint paths in split graphs ⋮ On the parameterized complexity of finding separators with non-hereditary properties ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ An Improved Kernel for Planar Connected Dominating Set ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ A linear kernel for planar red-blue dominating set ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\) ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ Algorithmic meta-theorems for restrictions of treewidth ⋮ A linear kernel for a planar connected dominating set ⋮ Minimum fill-in of sparse graphs: kernelization and approximation ⋮ Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms ⋮ On the small cycle transversal of planar graphs ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Contraction obstructions for treewidth ⋮ Unnamed Item ⋮ On the Small Cycle Transversal of Planar Graphs ⋮ Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ The Parameterized Complexity of Graph Cyclability ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ Parameterized Complexity of Vertex Deletion into Perfect Graph Classes ⋮ FPT is characterized by useful obstruction sets ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Planar k-Path in Subexponential Time and Polynomial Space ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: (Meta) Kernelization