Kernelization Lower Bounds Through Colors and IDs
From MaRDI portal
Publication:4962171
DOI10.1145/2650261zbMath1398.68226OpenAlexW2052712469MaRDI QIDQ4962171
Saket Saurabh, Daniel Lokshtanov, Michael Dom
Publication date: 30 October 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2650261
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (59)
On polynomial kernels for sparse integer linear programs ⋮ On the Complexity of Broadcast Domination and Multipacking in Digraphs ⋮ Hans Bodlaender and the Theory of Kernelization Lower Bounds ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Polynomial kernels and user reductions for the workflow satisfiability problem ⋮ Unnamed Item ⋮ On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ Parameterized complexity of graph burning ⋮ Unique Covering Problems with Geometric Sets ⋮ Reoptimization of parameterized problems ⋮ Sparsification upper and lower bounds for graph problems and not-all-equal SAT ⋮ On kernelization and approximation for the vector connectivity problem ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover} ⋮ Parameterized aspects of strong subgraph closure ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ The structural complexity landscape of finding balance-fair shortest paths ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ Building large \(k\)-cores from sparse graphs ⋮ Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ Essentially tight kernels for (weakly) closed graphs ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Exploiting hidden structure in selecting dimensions that distinguish vectors ⋮ Balanced substructures in bicolored graphs ⋮ Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms ⋮ Circumventing connectivity for kernelization ⋮ Unnamed Item ⋮ Constrained hitting set problem with intervals ⋮ Parameterized Complexity of Safe Set ⋮ How Bad is the Freedom to Flood-It? ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ On the complexity of broadcast domination and multipacking In digraphs ⋮ Dual parameterization of Weighted Coloring ⋮ Parameterized Complexity of Graph Burning ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ On the approximate compressibility of connected vertex cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity of independency and cliquy trees ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ Finding large degree-anonymous subgraphs is hard ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ Lower bounds for the happy coloring problems ⋮ The Maximum Colorful Arborescence problem parameterized by the structure of its color hierarchy graph ⋮ Unnamed Item ⋮ On approximate preprocessing for domination and hitting subgraphs with connected deletion sets ⋮ Exact multi-covering problems with geometric sets ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem ⋮ Refined parameterizations for computing colored cuts in edge-colored graphs ⋮ Dual parameterization of weighted coloring ⋮ Twin-width and polynomial kernels ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ Eternal vertex cover on bipartite graphs
This page was built for publication: Kernelization Lower Bounds Through Colors and IDs
