Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems

DOI10.1007/978-3-319-26626-8_31zbMath1473.68095arXiv1507.06341OpenAlexW2282490368MaRDI QIDQ3467861

Naveen Sivadasan, R. B. Sandeep, N. R. Aravind

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Dichotomy Results on the Hardness of $H$-free Edge Modification Problems

Cites Work

• Unnamed Item
• Graph-based data clustering with overlaps
• Correlation clustering
• Cluster editing with locally bounded modifications
• The node-deletion problem for hereditary properties is NP-complete
• Which problems have strongly exponential complexity?
• A polynomial kernel for trivially perfect editing
• Incompressibility of \(H\)-free edge modification problems
• The complexity of some edge deletion problems
• Edge-Deletion Problems
• On intervalizing \(k\)-colored graphs for DNA physical mapping

This page was built for publication: Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems