Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
type: Item
instance of: scholarly article
title: Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
author: Marin Bougeret
author: Ignasi Sau
author: Júlio Araújo
author: Victor Campos
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/2102.02484
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7608294
zbMATH Keywords: parameterized complexity
zbMATH Keywords: polynomial kernel
zbMATH Keywords: kernelization lower bound
zbMATH Keywords: maximum minimal vertex cover
zbMATH Keywords: Erdös-Hajnal property
zbMATH Keywords: induced subgraphs
MaRDI profile type: Publication
OpenAlex ID: W4281679364
cites work: Approximation Algorithms Inspired by Kernelization Methods
cites work: On domination and independent domination numbers of a graph
cites work: Ramsey-type theorems with forbidden subgraphs
cites work: Easy problems for tree-decomposable graphs
cites work: The many facets of upper domination
cites work: Kernel(s) for problems with no kernel
cites work: Approximation in (Poly-) Logarithmic Space
cites work: On problems without polynomial kernels
cites work: (Meta) Kernelization
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Kernel bounds for disjoint cycles and disjoint paths
cites work: Independent domination in finitely defined classes of graphs
cites work: Time-approximation trade-offs for inapproximable problems
cites work: Sparsification and subexponential approximation
cites work: Q5874491
cites work: On the max min vertex cover problem
cites work: (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
cites work: Extension of Vertex Cover and Independent Set in some classes of graphs
cites work: Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
cites work: The Erdős-Hajnal conjecture. A survey
cites work: The Erdős-Hajnal conjecture for bull-free graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: The vectorization of ITPACK 2C
cites work: Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
cites work: Q5743378
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Fundamentals of parameterized complexity
cites work: Ramsey-type theorems
cites work: Kernelization
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Q4198056
cites work: Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)
cites work: Independent domination in graphs: A survey and recent results
cites work: Independent dominating sets in triangle-free graphs
cites work: Safe Approximation and Its Relation to Kernelization
cites work: Independent domination in triangle-free graphs
cites work: Q5743381
cites work: Approximating minimum independent dominating sets in wireless networks
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
cites work: Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
cites work: Lossy kernelization
cites work: Q3291034
cites work: The four-colour theorem
cites work: On graphs with equal domination and independent domination numbers
cites work: The Design of Approximation Algorithms
cites work: The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
cites work: Maximum Minimal Vertex Cover Parameterized by Vertex Cover
DOI: 10.1007/S00453-022-00979-Z
description: scientific article; zbMATH DE number 7608294