An induced minor of a graph G is a graph H obtainable from G by deleting vertices and contracting edges, encoded by an induced minor model that assigns each vertex of H a connected bag of vertices in G, with bags adjacent exactly when the corresponding H-vertices are. This concept covers structural conditions on H — notably the S-non-trivial property, under which a model exists with all but a bounded set of bags trivial — that make detecting H as an induced minor solvable in polynomial time, the graph families (flowers, generalized houses and bulls, complete split graphs) satisfying them, and the fact that excluding long induced paths from the host graph makes detection tractable for every fixed H.
This paper studies the H-Induced Minor Containment problem (H-IMC): for a fixed graph H, deciding whether an input graph G contains H as an induced minor, meaning H can be obtained from G by deleting…