Meta-kernelization with structural parameters

DOI10.1016/j.jcss.2015.08.003zbMath1346.68109OpenAlexW1903283433WikidataQ124813044 ScholiaQ124813044MaRDI QIDQ896025

Stefan Szeider, Friedrich Slivovsky, Robert Ganian

Publication date: 11 December 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2015.08.003

zbMATH Keywords

monadic second-order logicmodular decompositionclique-widthparameterized complexitykernelizationrank-widthBoolean width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Decidability of theories and sets of sentences (03B25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A Retrospective on (Meta) Kernelization, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, Meta-kernelization using well-structured modulators, On structural parameterizations of the bounded-degree vertex deletion problem, Measuring what matters: a hybrid approach to dynamic programming with treewidth, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds on kernelization
• Guarantees and limits of preprocessing in constraint satisfaction and reasoning
• Infeasibility of instance compression and succinct PCPs for NP
• Elements of finite model theory.
• Boolean-width of graphs
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Algorithmic aspects of a general modular decomposition theory
• On problems without polynomial kernels
• Partitive hypergraphs
• Graph minors. X: Obstructions to tree-decomposition
• Algorithmic meta-theorems for restrictions of treewidth
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Linear time solvable optimization problems on graphs of bounded clique-width
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Kernelization Using Structural Parameters on Sparse Graph Classes
• Kernelization – Preprocessing with a Guarantee
• Linear Time Split Decomposition Revisited
• Easy problems for tree-decomposable graphs
• Kernels: Annotated, Proper and Induced
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization
• Decomposition of Directed Graphs
• (Meta) Kernelization
• Meta-kernelization using Well-structured Modulators
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Finding Branch-Decompositions and Rank-Decompositions