Cross-composition: a new technique for kernelization lower bounds
From MaRDI portal
Recommendations
Cited in
(55)- Two edge modification problems without polynomial kernels
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- Parameterized complexity of a coupled-task scheduling problem
- A multivariate analysis of the strict terminal connection problem
- Kernelization lower bound for permutation pattern matching
- On the hardness of losing width
- Parameterized complexity of Eulerian deletion problems
- Parameterized algorithms for load coloring problem
- Parameterized complexity of firefighting
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- FPT and kernelization algorithms for the induced tree problem
- Perfectly matched sets in graphs: parameterized and exact computation
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- FPT is characterized by useful obstruction sets
- Parameterized Complexity of Firefighting Revisited
- On polynomial kernels for structural parameterizations of odd cycle transversal
- Kernel bounds for path and cycle problems
- On the hardness of losing width
- On cutwidth parameterized by vertex cover
- Kernelization -- preprocessing with a guarantee
- On structural parameterizations of graph motif and chromatic number
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Data reduction for graph coloring problems
- Parameterized complexity of Eulerian deletion problems
- The Flood-It game parameterized by the vertex cover number
- New limits to classical and quantum instance compression
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Kernel bounds for path and cycle problems
- Data reduction for graph coloring problems
- Fractals for kernelization lower bounds, with an application to length-bounded cut problems
- Fractals for kernelization lower bounds
- Confronting intractability via parameters
- On cutwidth parameterized by vertex cover
- Restricted and swap common superstring: a multivariate algorithmic perspective
- Kernelization Lower Bounds by Cross-Composition
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- An approximate kernel for connected feedback vertex set
- Kernelization of packing problems
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
- Disconnected matchings
- Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization
- Weighted connected matchings
- Kernel bounds for disjoint cycles and disjoint paths
- Kernelization dichotomies for hitting subgraphs under structural parameterizations
- Parameterized lower bounds for the weighted vertex cover problem in trees
- Weighted connected matchings
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Matching (multi)cut: algorithms, complexity, and enumeration
- Kernelization of compressing two-dimensional routing tables with order
- Chromatic index under parameterized settings
- On the parameterized complexity of odd coloring
- Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
This page was built for publication: Cross-composition: a new technique for kernelization lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3113681)
