Meta-kernelization with structural parameters

DOI10.1016/j.jcss.2015.08.003zbMath1346.68109WikidataQ124813044 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 logic; modular decomposition; clique-width; parameterized complexity; kernelization; rank-width; Boolean width

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W05: Nonnumerical algorithms

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

03B25: Decidability of theories and sets of sentences

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

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