Detecting induced star-like minors in polynomial time

Fiala, J.; Kaminksi, M.; Paulusma, D.

Abstract

The Induced Minor problem is to test whether a graph G contains a graph H as an induced minor, i.e., if G can be modified into H by a sequence of vertex deletions and edge contractions. When H is fixed, i.e., not part of the input, this problem is denoted H-Induced Minor. We provide polynomial-time algorithms for this problem in the case that the fixed target graph has a star-like structure. In particular, we show polynomial-time solvability for all forests H on at most seven vertices except for one such case.

Citation

Fiala, J., Kaminksi, M., & Paulusma, D. (2012). Detecting induced star-like minors in polynomial time. Journal of discrete algorithms, 17, 74-85. https://doi.org/10.1016/j.jda.2012.11.002

• Journal Article Type: Article
• Publication Date: Dec 1, 2012
• Deposit Date: Mar 11, 2013
• Publicly Available Date: Apr 17, 2013
• Journal: Journal of Discrete Algorithms
• Print ISSN: 1570-8667
• Electronic ISSN: 1570-8675
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 17
• Pages: 74-85
• DOI: https://doi.org/10.1016/j.jda.2012.11.002
• Keywords: Induced minor, Tree, Computational complexity.
• Public URL: https://durham-repository.worktribe.com/output/1495906