Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds

DOI10.1007/s00453-022-00979-zOpenAlexW4281679364MaRDI QIDQ2093577

Marin Bougeret, Ignasi Sau, Julio Araujo, Victor A. Campos

Publication date: 27 October 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.02484

zbMATH Keywords

induced subgraphsparameterized complexitypolynomial kernelErdös-Hajnal propertykernelization lower boundmaximum minimal vertex cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Independent dominating sets in triangle-free graphs
• Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover
• On the max min vertex cover problem
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Ramsey-type theorems
• On domination and independent domination numbers of a graph
• Independent domination in triangle-free graphs
• The Erdős-Hajnal conjecture for bull-free graphs
• Approximating minimum independent dominating sets in wireless networks
• On problems without polynomial kernels
• On graphs with equal domination and independent domination numbers
• The four-colour theorem
• Independent domination in finitely defined classes of graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• Time-approximation trade-offs for inapproximable problems
• Sparsification and subexponential approximation
• The many facets of upper domination
• Independent domination in graphs: A survey and recent results
• Linear time solvable optimization problems on graphs of bounded clique-width
• Extension of Vertex Cover and Independent Set in some classes of graphs
• Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs
• The Erdös-Hajnal Conjecture-A Survey
• Safe Approximation and Its Relation to Kernelization
• Approximation Algorithms Inspired by Kernelization Methods
• The Design of Approximation Algorithms
• (Meta) Kernelization
• Kernel(s) for problems with no kernel
• The vectorization of ITPACK 2C
• Easy problems for tree-decomposable graphs
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• Maximum Minimal Vertex Cover Parameterized by Vertex Cover
• Kernelization
• Lossy kernelization
• Kernelization Lower Bounds by Cross-Composition
• Approximation in (Poly-) Logarithmic Space
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation)
• Ramsey-type theorems with forbidden subgraphs