Incompressibility of H-free edge modification problems: towards a dichotomy

DOI10.4230/LIPICS.ESA.2020.72MaRDI QIDQ5874544FDOQ5874544

Authors: Dániel Marx, R. B. Sandeep 

Publication date: 7 February 2023

Recommendations

• Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
• Incompressibility of \(H\)-free edge modification problems
• Incompressibility of \(H\)-free edge modification
• A polynomial kernel for diamond-free editing
• A Polynomial Kernel for Diamond-Free Editing

zbMATH Keywords

incompressibilityH-free graphsedge modification problems

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Fixed-parameter tractability of graph modification problems for hereditary properties
• The node-deletion problem for hereditary properties is NP-complete
• Parameterized algorithms
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Node-Deletion Problems on Bipartite Graphs
• Chordal editing is fixed-parameter tractable
• Title not available (Why is that?)
• Edge-Deletion Problems
• Title not available (Why is that?)
• Cluster editing: kernelization based on edge cuts
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Kernelization. Theory of parameterized preprocessing
• Incompressibility of \(H\)-free edge modification problems
• Parameterized lower bounds and dichotomy results for the NP-completeness of \(H\)-free edge modification problems
• Polynomial kernelization for removing induced claws and diamonds
• A Polynomial Kernel for Diamond-Free Editing
• Dichotomy results on the hardness of \(H\)-free edge modification problems

Cited In (2)

• Kernel for \(K_t\)\textsc-free Edge Deletion
• Title not available (Why is that?)

This page was built for publication: Incompressibility of \(H\)-free edge modification problems: towards a dichotomy

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