A polynomial kernel for diamond-free editing

DOI10.1007/S00453-021-00891-YMaRDI QIDQ2072105zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• A Polynomial Kernel for Diamond-Free Editing
• Parameterized lower bound and improved kernel for diamond-free edge deletion
• Two edge modification problems without polynomial kernels
• On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion
• Incompressibility of \(H\)-free edge modification problems

Cites work

• A kernelization algorithm for \(d\)-hitting set
• Cluster editing: kernelization based on edge cuts
• Dichotomy results on the hardness of \(H\)-free edge modification problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fundamentals of parameterized complexity
• Hardness of approximation for \(H\)-free edge modification problems
• Incompressibility of \(H\)-free edge modification problems
• Intersection Theorems for Systems of Sets
• Node-Deletion Problems on Bipartite Graphs
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• On the complexity of \(k\)-SAT
• Parameterized lower bound and improved kernel for diamond-free edge deletion
• Parametrized complexity theory.
• Polynomial kernels for paw-free edge modification problems
• The complexity of some edge deletion problems
• The node-deletion problem for hereditary properties is NP-complete
• Two edge modification problems without polynomial kernels

Cited in

(7)

• Cutting a tree with subgraph complementation is hard, except for some small trees
• Cutting a tree with subgraph complementation is hard, except for some small trees
• A Polynomial Kernel for Diamond-Free Editing
• Parameterized lower bound and improved kernel for diamond-free edge deletion
• A survey of parameterized algorithms and the complexity of edge modification
• Polynomial kernelization for removing induced claws and diamonds
• Polynomial kernelization for removing induced claws and diamonds

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2072105)