Graph editing to a fixed target

Golovach, P.; 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. A. (2013, December). Graph editing to a fixed target. Presented at International Workshop on Combinatorial Algorithms, Rouen, France

• Presentation Conference Type: Conference Paper (published)
• Conference Name: International Workshop on Combinatorial Algorithms
• Publication Date: Jan 1, 2013
• Deposit Date: Jun 27, 2013
• Publicly Available Date: Jan 15, 2015
• Print ISSN: 0302-9743
• Pages: 192-205
• Series Title: Lecture notes in computer science
• Series Number: 8288
• Series ISSN: 0302-9743,1611-3349
• Book Title: Combinatorial algorithms : 24th International Workshop, IWOCA 2013, 10-12 July 2013, Rouen, France ; revised selected papers.
• ISBN: 9783642452772
• DOI: https://doi.org/10.1007/978-3-642-45278-9_17
• Public URL: https://durham-repository.worktribe.com/output/1156284