(Meta) Kernelization

DOI10.1145/2973749zbMath1425.68137OpenAlexW2563156040WikidataQ59567396 ScholiaQ59567396MaRDI QIDQ3177820

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

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://hal-lirmm.ccsd.cnrs.fr/lirmm-01483628/file/0904.0727.pdf

zbMATH Keywords

monadic second-order logictreewidthembedded graphsparameterized complexitykernelizationpreprocessingfinite integer indexprotrusions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Logic in computer science (03B70)

Related Items (46)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Compactors for parameterized counting problems ⋮ Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ A Retrospective on (Meta) Kernelization ⋮ Unnamed Item ⋮ Parameterized analysis and crossing minimization problems ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Lower bounds for protrusion replacement by counting equivalence classes ⋮ Sparse obstructions for minor-covering parameters ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ Meta-kernelization using well-structured modulators ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Treelength of series-parallel graphs ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ Unnamed Item ⋮ Maximum Cut Parameterized by Crossing Number ⋮ Unnamed Item ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ Reducing CMSO model checking to highly connected graphs ⋮ Explicit linear kernels for packing problems ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Kernels for packing and covering problems ⋮ Unnamed Item ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ Editing to a planar graph of given degrees ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Bidimensionality and Kernels ⋮ Modification to Planarity is Fixed Parameter Tractable ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ Lean Tree-Cut Decompositions: Obstructions and Algorithms ⋮ On approximate preprocessing for domination and hitting subgraphs with connected deletion sets ⋮ Lossy Kernels for Hitting Subgraphs ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size ⋮ Partial vertex cover on graphs of bounded degeneracy ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

This page was built for publication: (Meta) Kernelization