2024/12/30 by Dallard, Clément, Dumas, Maël, Hilaire, Claire +1 · 1 citation
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2501.00161
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. Equivalently, the problem asks if there exists an induced minor model of H in G, that is, a collection of disjoint subsets of vertices of G, each inducing a connected subgraph, such that contracting each subgraph into a single vertex results in H. It is known that H-IMC is NP-complete for several graphs H, even when H is a tree. In this work, we investigate which properties of H guarantee the existence of an induced minor model whose structure can be leveraged to solve the problem in polynomial time. This allows us to identify four infinite families of graphs H that enjoy such properties. 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.