Further parameterized algorithms for the F-free edge deletion problem

DOI10.1016/J.TCS.2022.08.025MaRDI QIDQ2676471zbMATH OpenOpenAlexFDO

Authors Ajinkya Gaikwad, Soumen Maity

Publication date 27 September 2022

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

Full work available at URL https://doi.org/10.1016/j.tcs.2022.08.025

zbMATH Keywords

treewidthparameterized complexityFPTvertex cover numberW[1-hard]

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Parameterized lower bound and NP-completeness of some \(H\)-free edge deletion problems
• Parameterized algorithms for deletion to \((r,\ell)\)-graphs
• The complexity of some edge deletion problems
• A parameterized algorithm for bounded-degree vertex deletion
• Parameterized algorithms on perfect graphs for deletion to \((r,\ell)\)-graphs
• Parameterized lower bound and improved kernel for diamond-free edge deletion
• On structural parameterizations of the bounded-degree vertex deletion problem
• On structural parameterizations of the bounded-degree vertex deletion problem
• Faster parameterized algorithms for two vertex deletion problems
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes

Cites work

• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A unified approximation algorithm for node-deletion problems
• Complexity classification of some edge modification problems
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Faster parameterized algorithms for deletion to split graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph Layout Problems Parameterized by Vertex Cover
• Graph minors. III. Planar tree-width
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• Node-and edge-deletion NP-complete problems
• On the NP-hardness of edge-deletion and -contraction problems
• On the hardness of approximating minimization problems
• Parameterized algorithms
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Which problems have strongly exponential complexity?

Cited in

(1)

• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs

This page was built for publication: Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem

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