Graph editing to a fixed target

Golovach, P.A.; Paulusma, D.; Stewart, I.A.

Abstract

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.

Citation

Golovach, P., Paulusma, D., & Stewart, I. (2017). Graph editing to a fixed target. Discrete Applied Mathematics, 216(Part 1), 181-190. https://doi.org/10.1016/j.dam.2014.07.008

• Journal Article Type: Article
• Acceptance Date: Jul 20, 2014
• Online Publication Date: Aug 7, 2014
• Publication Date: Jan 10, 2017
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Jan 6, 2015
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 216
• Issue: Part 1
• Pages: 181-190
• DOI: https://doi.org/10.1016/j.dam.2014.07.008
• Keywords: Graph editing, Graph containment relation, Computational complexity.
• Related Public URLs: http://community.dur.ac.uk/i.a.stewart/Papers/graphedit.pdf