Smaller kernels for two vertex deletion problems

DOI10.1016/j.ipl.2024.106493zbMATH Open1540.682MaRDI QIDQ6551719

Dekel Tsur

Publication date: 7 June 2024

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

graph algorithmsparameterized complexitykernelization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• The node-deletion problem for hereditary properties is NP-complete
• An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
• Faster algorithm for pathwidth one vertex deletion
• A polynomial kernel for block graph deletion
• Hitting forbidden minors: approximation and kernelization
• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• A Quartic Kernel for Pathwidth-One Vertex Deletion
• Graph Classes: A Survey

This page was built for publication: Smaller kernels for two vertex deletion problems