标题： 多项式时间检测诱导子图的充分条件 显示英文标题

标题： Sufficient conditions for polynomial-time detection of induced minors

摘要： $H$-诱导小图包含问题($H$-IMC)是判断一个固定图$H$是否为作为输入给出的图$G$的诱导小图，即$H$是否可以通过删除顶点和收缩边从$G$得到。 已知几个图$H$对于$H$-IMC 是 NP 完全的，即使$H$是一棵树。 在本文中，我们研究对$H$和$G$的哪些条件是足够的，使得该问题变为多项式时间可解的。 我们的结果识别出三个无限图类，如果$H$属于这些类中的一个，则$H$-IMC 可以在多项式时间内求解。 此外，我们证明如果输入图$G$排除长的诱导路径，那么对于任何固定的图$H$，$H$-IMC 在多项式时间内可解。作为我们结果的副产品，这表明对于所有具有最多$5$个顶点的图$H$，$H$-IMC 在多项式时间内可解，除了三个未解决的情况。 显示英文摘要

摘要： 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.