Publication details for Professor Iain StewartGolovach, P., Paulusma, D. & Stewart, I.A. (2013), Graph editing to a fixed target, in Lecroq, T. & Mouchard, L. eds, Lecture Notes in Computer Science 8288: International Workshop on Combinatorial Algorithms. Rouen, France, Springer, Rouen, 192-205.
- Publication type: Conference Paper
- ISSN/ISBN: 978-3-642-45277-2 (paperback), 978-3-642-45278-9 (online)
- DOI: 10.1007/978-3-642-45278-9_17
- Further publication details on publisher web site
- Durham Research Online (DRO) - 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.