Sufficient Conditions for Polynomial-Time Detection of Induced Minors
摘要
The H-Induced Minor Containment problem (H-IMC) consists in deciding if a fixed graph H is an induced minor of a graph G given as input, that is, whether H can be obtained from G by deleting vertices and contracting edges. Several graphs H are known for which H-IMC is NP-complete, even when H is a tree. In this paper, we investigate which conditions on H and G are sufficient so that the problem becomes polynomial-time solvable. Our results identify three infinite classes of graphs such that, if H belongs to one of these classes, then H-IMC can be solved in polynomial time. Moreover, we show that if the input graph G excludes long induced paths, then H-IMC is polynomial-time solvable for any fixed graph H. As a byproduct of our results, this implies that H-IMC is polynomial-time solvable for all graphs H with at most 5 vertices, except for three open cases.