A polynomial kernel for diamond-free editing

DOI10.1007/s00453-021-00891-yOpenAlexW3214811907MaRDI QIDQ2072105

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

Publication date: 1 February 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9473/

zbMATH Keywords

kernelizationdiamond-free graphgraph modification problem\(H\)-free editing

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (2)

A survey of parameterized algorithms and the complexity of edge modification ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees

Cites Work

• Fundamentals of parameterized complexity
• A kernelization algorithm for \(d\)-hitting set
• 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
• Node-Deletion Problems on Bipartite Graphs
• Hardness of Approximation for H -free Edge Modification Problems
• Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
• Polynomial kernels for paw-free edge modification problems
• On the complexity of \(k\)-SAT

This page was built for publication: A polynomial kernel for diamond-free editing