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

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

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

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 4 k ² 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?)
• Title not available (Why is that?)
• A cubic kernel for feedback vertex set and loop cutset
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
• Kernelization
• Title not available (Why is that?)
• Title not available (Why is that?)

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)