Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems

DOI10.1007/978-3-662-49529-2_7zbMath1415.68155arXiv1509.08807OpenAlexW2276482067MaRDI QIDQ2802929

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

Publication date: 3 May 2016

Published in: LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

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

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)

Related Items (6)

Parameterizing edge modification problems above lower bounds ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Dichotomy Results on the Hardness of $H$-free Edge Modification Problems ⋮ Unnamed Item ⋮ Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy

This page was built for publication: Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems