Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds

DOI10.1007/978-3-030-42071-0_8OpenAlexW3020027665MaRDI QIDQ5042452FDOQ5042452

Authors: Bart M. P. Jansen 

Publication date: 19 October 2022

Published in: Treewidth, Kernels, and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-42071-0_8

Recommendations

• Kernelization Lower Bounds by Cross-Composition
• Cross-composition: a new technique for kernelization lower bounds
• Hans Bodlaender and the Theory of Kernelization Lower Bounds
• Fractals for kernelization lower bounds, with an application to length-bounded cut problems
• Lower bounds for kernelization

zbMATH Keywords

graph problemskernelization lower boundscross-composition

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Reducibility among combinatorial problems
• On the Complexity of General Graph Factor Problems
• On problems without polynomial kernels
• The node-deletion problem for hereditary properties is NP-complete
• Parametrized complexity theory.
• A \(4k^2\) kernel for feedback vertex set
• Parameterized algorithms
• Vertex packings: Structural properties and algorithms
• Kernelization lower bounds through colors and IDs
• Kernelization Lower Bounds by Cross-Composition
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Infeasibility of instance compression and succinct PCPs for NP
• Title not available (Why is that?)
• Nondeterminism within $P^ * $
• Kernel bounds for disjoint cycles and disjoint paths
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Title not available (Why is that?)
• Kernelization of packing problems
• A cubic kernel for feedback vertex set and loop cutset
• Cross-composition: a new technique for kernelization lower bounds
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Kernel bounds for path and cycle problems
• Title not available (Why is that?)
• A Cubic Kernel for Feedback Vertex Set
• On Problems without Polynomial Kernels (Extended Abstract)
• The power of primitive positive definitions with polynomially many variables
• Linear-time kernelization for feedback vertex set
• Optimal sparsification for some binary CSPs using low-degree polynomials
• Kernelization. Theory of parameterized preprocessing
• Title not available (Why is that?)
• Best-case and worst-case sparsifiability of Boolean CSPs

This page was built for publication: Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds

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