A Polynomial Kernel for Diamond-Free Editing

DOI10.4230/LIPIcs.ESA.2018.10OpenAlexW2964245960MaRDI QIDQ5009567

Yixin Cao, Ashutosh Rai, Junjie Ye, R. B. Sandeep

Publication date: 4 August 2021

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

zbMATH Keywords

kernelizationgraph modification problemdiamond-free\(H\)-free editing

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (7)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Kernel for \(K_t\)\textsc{-free Edge Deletion} ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Polynomial kernels for paw-free edge modification problems ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy

Cites Work

• Fundamentals of parameterized complexity
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Two edge modification problems without polynomial kernels
• Cluster editing: kernelization based on edge cuts
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Incompressibility of \(H\)-free edge modification problems
• Parametrized complexity theory.
• Intersection Theorems for Systems of Sets
• The complexity of some edge deletion problems
• Edge-Deletion Problems
• Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
• On the complexity of \(k\)-SAT

This page was built for publication: A Polynomial Kernel for Diamond-Free Editing