1. Sufficient conditions for polynomial-time detection of induced minors
- Author
-
Dallard, Clément, Dumas, Maël, Hilaire, Claire, and Perez, Anthony
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,Computer Science - Discrete Mathematics ,Mathematics - Combinatorics - Abstract
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.
- Published
- 2024