{"id":"arxiv/2604.24216","url":"https://arxiv.org/abs/2604.24216","tags":["math.CO","cs.CC","cs.DS"],"score":0,"title":"On Detecting $H$-Induced Minors for Small $H$","domain":"math.CO","source":"arxiv","authors":["Tala Eagling-Vose","Barnaby Martin","Daniël Paulusma","Nicolas Trotignon"],"reviews":0,"subject":"math.CO","summary":"We consider the $H$-Induced Minor problem: for a fixed graph~$H$, decide whether a given graph $G$ contains $H$ as an induced minor. While the problem is known to be NP-complete for some trees~$H$ on more than $2^{300}$ vertices, the complexity for small trees remains unresolved. In particular, the case where $H$ is the $7$-vertex tree consisting of a path on five vertices with a pendant vertex attached to the second and fourth vertex was a long-standing open problem. We show that this case is polynomial-time solvable by developing algorithms that detect a sequence of carefully chosen…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-27","reactions":{}}