Publication details for Professor Iain StewartGolovach, P.A., Paulusma, D. & Stewart, I.A. (2017). Graph editing to a fixed target. Discrete Applied Mathematics 216(Part 1): 181-190.
- Publication type: Journal Article
- ISSN/ISBN: 0166-218X
- DOI: 10.1016/j.dam.2014.07.008
- Keywords: Graph editing, Graph containment relation, Computational complexity
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
- View in another repository - may include full text
Author(s) from Durham
For a fixed graph H, the H-Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the H-Topological Minor Edit problem. For each problem we show polynomial-time solvable and NP-complete cases depending on the choice of H. Moreover, when G is AT-free, chordal or planar, we show that H-Minor Edit is polynomial-time solvable for all graphs H.