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)
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
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 ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ On data reduction for dynamic vector bin packing ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ Colouring a dominating set without conflicts: \(q\)-subset square colouring ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Unnamed Item ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs ⋮ On the relation of strong triadic closure and cluster deletion ⋮ The clever shopper problem ⋮ Parameterized certificate dispersal and its variants ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ 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 ⋮ Structural parameterizations of budgeted graph coloring ⋮ On structural parameterizations of firefighting
This page was built for publication: Kernelization Lower Bounds by Cross-Composition
