Kernelization Lower Bounds by Cross-Composition
From MaRDI portal
Abstract: We introduce the cross-composition framework for proving kernelization lower bounds. A classical problem L AND/OR-cross-composes into a parameterized problem Q if it is possible to efficiently construct an instance of Q with polynomially bounded parameter value that expresses the logical AND or OR of a sequence of instances of L. Building on work by Bodlaender et al. (ICALP 2008) and using a result by Fortnow and Santhanam (STOC 2008) with a refinement by Dell and van Melkebeek (STOC 2010), we show that if an NP-hard problem OR-cross-composes into a parameterized problem Q then Q does not admit a polynomial kernel unless NP subseteq coNP/poly and the polynomial hierarchy collapses. Similarly, an AND-cross-composition for Q rules out polynomial kernels for Q under Bodlaender et al.'s AND-distillation conjecture. Our technique generalizes and strengthens the recent techniques of using composition algorithms and of transferring the lower bounds via polynomial parameter transformations. We show its applicability by proving kernelization lower bounds for a number of important graphs problems with structural (non-standard) parameterizations, e.g., Clique, Chromatic Number, Weighted Feedback Vertex Set, and Weighted Odd Cycle Transversal do not admit polynomial kernels with respect to the vertex cover number of the input graphs unless the polynomial hierarchy collapses, contrasting the fact that these problems are trivially fixed-parameter tractable for this parameter. After learning of our results, several teams of authors have successfully applied the cross-composition framework to different parameterized problems. For completeness, our presentation of the framework includes several extensions based on this follow-up work. For example, we show how a relaxed version of OR-cross-compositions may be used to give lower bounds on the degree of the polynomial in the kernel size.
Recommendations
- Cross-composition: a new technique for kernelization lower bounds
- Lower bounds on kernelization
- Lower bounds for kernelization
- scientific article; zbMATH DE number 7053262
- Lower bounds for kernelizations and other preprocessing procedures
- Lower bounds for kernelizations and other preprocessing procedures
- Kernelization: new upper and lower bound techniques
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Computing kernels in parallel: lower and upper bounds
- Kernelization techniques and its applications to parameterized computation
Cited in
(only showing first 100 items - show all)- On problems without polynomial kernels
- Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
- Two edge modification problems without polynomial kernels
- On the kernelization complexity of string problems
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- Parameterized complexity of machine scheduling: 15 open problems
- Finding temporal paths under waiting time constraints
- On the approximate compressibility of connected vertex cover
- On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Sliding window temporal graph coloring
- On fixed-order book thickness parameterized by the pathwidth of the vertex ordering
- On some FPT problems without polynomial Turing compressions
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Parameterized complexity of set-restricted disjoint paths on chordal graphs
- Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
- Streaming deletion problems parameterized by vertex cover
- Structural parameterization for minimum conflict-free colouring
- Parameterized aspects of strong subgraph closure
- Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
- On structural parameterizations of the bounded-degree vertex deletion problem
- Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
- On explaining integer vectors by few homogeneous segments
- Optimal data reduction for graph coloring using low-degree polynomials
- Turing kernelization for finding long paths in graph classes excluding a topological minor
- Alternative parameterizations of \textsc{Metric Dimension}
- On the computational complexity of length- and neighborhood-constrained path problems
- On the parameterized complexity of graph modification to first-order logic properties
- A multivariate analysis of the strict terminal connection problem
- Consensus strings with small maximum distance and small distance sum
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- Polynomial kernels for vertex cover parameterized by small degree modulators
- The parameterized complexity of the minimum shared edges problem
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Two edge-disjoint paths with length constraints
- A completeness theory for polynomial (Turing) kernelization
- Incompressibility of \(H\)-free edge modification problems
- On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
- A complete parameterized complexity analysis of bounded planning
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- The graph motif problem parameterized by the structure of the input graph
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- On kernelization and approximation for the vector connectivity problem
- Parameterized complexity of secluded connectivity problems
- Meta-kernelization using well-structured modulators
- On the complexity of restoring corrupted colorings
- Edge-disjoint packing of stars and cycles
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- The structural complexity landscape of finding balance-fair shortest paths
- On 2-clubs in graph-based data clustering: theory and algorithm engineering
- On polynomial kernels for sparse integer linear programs
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
- FPT is characterized by useful obstruction sets
- A completeness theory for polynomial (Turing) kernelization
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
- Clique Cover and Graph Separation
- Win-win kernelization for degree sequence completion problems
- Finding shortest paths between graph colourings
- Cross-composition: a new technique for kernelization lower bounds
- Finding two edge-disjoint paths with length constraints
- Edge-disjoint packing of stars and cycles
- Lower bounds on kernelization
- Fractals for kernelization lower bounds, with an application to length-bounded cut problems
- Fractals for kernelization lower bounds
- On the parameterized complexity of computing balanced partitions in graphs
- Parameterized Complexity of Conflict-Free Graph Coloring
- Consensus strings with small maximum distance and small distance sum
- A parameterized complexity view on collapsing \(k\)-cores
- Dual parameterization of weighted coloring
- Exploring the kernelization borders for hitting cycles
- Best-case and worst-case sparsifiability of Boolean CSPs
- Solving partition problems almost always requires pushing many vertices around
- On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
- Hans Bodlaender and the Theory of Kernelization Lower Bounds
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- Fixed-parameter algorithms for DAG partitioning
- Graph editing to a given degree sequence
- On 2-clubs in graph-based data clustering: theory and algorithm engineering
- On kernelization for edge dominating set under structural parameters
- Data-compression for parametrized counting problems on sparse graphs
- Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
- The Power of Linear-Time Data Reduction for Maximum Matching
- Smaller parameters for vertex cover kernelization
- Turing kernelization for finding long paths in graphs excluding a topological minor
- Graph motif problems parameterized by dual
- The parameterized complexity of motion planning for snake-like robots
- Parameterized complexity of critical node cuts
- Solving partition problems almost always requires pushing many vertices around
- A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees
- Graph editing to a given degree sequence
- 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
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- Structural parameterizations of budgeted graph coloring
- Fine-grained complexity of safety verification
- The clever shopper problem
- Structural parameterizations of budgeted graph coloring
This page was built for publication: Kernelization Lower Bounds by Cross-Composition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4979840)
