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

DOI10.1007/978-3-030-42071-0_8MaRDI QIDQ5042452zbMATH OpenOpenAlexFDO

Authors Bart M. P. Jansen

Publication date 19 October 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph problemskernelization lower boundscross-composition

Mathematics Subject Classification ID

Computer science (68-XX)

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

Cites work

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

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)