Polynomial kernels for paw-free edge modification problems

DOI10.1016/j.tcs.2021.08.015OpenAlexW3194498379MaRDI QIDQ5919117

Yixin Cao, Yuping Ke, Hanchun Yuan

Publication date: 21 October 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

kernelizationgraph modification problempaw-free graph

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (5)

Structural parameterization of cluster deletion ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ A polynomial kernel for diamond-free editing ⋮ On subgraph complementation to \(H\)-free Graphs

Cites Work

• Paw-free graphs
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Kernel for \(K_t\)\textsc{-free Edge Deletion}
• A Polynomial Kernel for Diamond-Free Editing
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
• Unnamed Item

This page was built for publication: Polynomial kernels for paw-free edge modification problems