Kernelization Lower Bounds by Cross-Composition
From MaRDI portal
Publication:4979840
DOI10.1137/120880240zbMath1295.05222arXiv1206.5941OpenAlexW2039100365WikidataQ59567471 ScholiaQ59567471MaRDI QIDQ4979840
Bart M. P. Jansen, Stefan Kratsch, Hans L. Bodlaender
Publication date: 19 June 2014
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1206.5941
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (only showing first 100 items - show all)
Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ On polynomial kernels for sparse integer linear programs ⋮ A parameterized complexity view on collapsing \(k\)-cores ⋮ Hans Bodlaender and the Theory of Kernelization Lower Bounds ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ Win-win kernelization for degree sequence completion problems ⋮ Edge-disjoint packing of stars and cycles ⋮ Streaming deletion problems parameterized by vertex cover ⋮ Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases ⋮ Finding shortest paths between graph colourings ⋮ AND-compression of NP-complete problems: streamlined proof and minor observations ⋮ Finding Two Edge-Disjoint Paths with Length Constraints ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ Polynomial kernels for weighted problems ⋮ Structural parameterization for minimum conflict-free colouring ⋮ Two edge modification problems without polynomial kernels ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ 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 ⋮ Clique Cover and Graph Separation ⋮ Parameterized complexity of superstring problems ⋮ Parameterized aspects of strong subgraph closure ⋮ Meta-kernelization using well-structured modulators ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Multidimensional Binary Vector Assignment Problem: Standard, Structural and Above Guarantee Parameterizations ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ The structural complexity landscape of finding balance-fair shortest paths ⋮ Interval scheduling and colorful independent sets ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ On the complexity of restoring corrupted colorings ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graph Motif Problems Parameterized by Dual ⋮ Fractals for Kernelization Lower Bounds ⋮ The Parameterized Complexity of Motion Planning for Snake-Like Robots ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Finding temporal paths under waiting time constraints ⋮ Dual parameterization of Weighted Coloring ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ Graph editing to a given degree sequence ⋮ On the kernelization complexity of string problems ⋮ Parameterized complexity of critical node cuts ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ On explaining integer vectors by few homogeneous segments ⋮ On the approximate compressibility of connected vertex cover ⋮ Graph Editing to a Given Degree Sequence ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ 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 ⋮ The Parameterized Complexity of Graph Cyclability ⋮ Parameterized Complexity of Conflict-Free Graph Coloring ⋮ On the computational complexity of length- and neighborhood-constrained path problems ⋮ On the parameterized complexity of graph modification to first-order logic properties ⋮ Solving Partition Problems Almost Always Requires Pushing Many Vertices Around ⋮ A multivariate analysis of the strict terminal connection problem ⋮ Consensus strings with small maximum distance and small distance sum ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph ⋮ Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees ⋮ On some FPT problems without polynomial Turing compressions ⋮ 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? ⋮ Smaller Parameters for Vertex Cover Kernelization ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor ⋮ The Power of Linear-Time Data Reduction for Maximum Matching ⋮ Two edge-disjoint paths with length constraints ⋮ Best-case and worst-case sparsifiability of Boolean CSPs ⋮ Dual parameterization of weighted coloring ⋮ Parameterized complexity of independent set in H-free graphs ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds ⋮ Parameterized complexity of set-restricted disjoint paths on chordal graphs ⋮ A completeness theory for polynomial (Turing) kernelization ⋮ On sparsification for computing treewidth ⋮ 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 ⋮ Editing to a graph of given degrees ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
This page was built for publication: Kernelization Lower Bounds by Cross-Composition
