Approximate Turing kernelization for problems parameterized by treewidth

DOI10.1016/J.JCSS.2025.103720MaRDI QIDQ6885363zbMATH OpenFDO

Authors Eva-Maria C. Hols, Stefan Kratsch, Astrid Pieterse

Publication date 11 December 2025

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.2025.103720

zbMATH Keywords

approximate kernelizationparameterized complexitytreewidthTuring kernelization

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• (Meta) kernelization
• \textsc{Planar} \(\mathcal{F}\)-\textsc{deletion}: approximation, kernelization and optimal FPT algorithms
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• A (3+)k-vertex kernel for edge-disjoint triangle packing
• A 4k^2 kernel for feedback vertex set
• A completeness theory for polynomial (Turing) kernelization
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• A hierarchy of polynomial kernels
• A polynomial kernel for diamond-free editing
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• A Problem Kernelization for Graph Packing
• Approximate Turing kernelization and lower bounds for domination problems
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Clique Cover and Graph Separation
• Connected graph searching
• Connected Treewidth and Connected Graph Searching
• Depth-first search and the vertex cover problem
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Kernel(s) for problems with no kernel
• Kernelization lower bounds through colors and IDs
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Kernelization. Theory of parameterized preprocessing
• Kernels for edge dominating set: simpler or smaller
• Lossy kernelization
• Lossy kernels for connected dominating set on sparse graphs
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• Mathematical Foundations of Computer Science 2004
• On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
• On kernelization for edge dominating set under structural parameters
• On problems without polynomial kernels
• On the lossy kernelization for connected treedepth deletion set
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Parameterized algorithms
• Parameterized and Exact Computation
• Polynomial Kernel for Interval Vertex Deletion
• Polynomial kernels for hitting forbidden minors under structural parameterizations
• Polynomial Turing compressions for some graph problems parameterized by modular-width
• Representative sets and irrelevant vertices: new tools for kernelization
• Towards optimal kernel for edge-disjoint triangle packing
• Turing kernelization for finding long paths and cycles in restricted graph classes
• Vertex cover: Further observations and further improvements
• Vertex packings: Structural properties and algorithms
• What Is Known About Vertex Cover Kernelization?

This page was built for publication: Approximate Turing kernelization for problems parameterized by treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6885363)