标题： 诱导小图模型。 II. 诱导小图的多项式时间检测的充分条件 显示英文标题

标题： Induced Minor Models. II. Sufficient conditions for polynomial-time detection of induced minors

摘要： $H$诱导的小图包含问题 ($H$-IMC) 是确定一个固定图$H$是否是作为输入给出的图$G$的诱导小图，即，是否可以从$G$通过删除顶点和收缩边得到$H$。 等价地，这个问题询问是否在$G$中存在$H$的诱导极小模型，即$G$的顶点不相交子集的集合，每个子集都诱导出一个连通子图，使得将每个子图收缩为一个顶点后得到$H$。已知对于某些图$H$，$H$-IMC 是 NP 完全的，即使$H$是一棵树。 在本工作中，我们研究$H$的哪些性质保证存在一个可以利用其结构在多项式时间内求解问题的诱导小图模型。 这使我们能够识别出四个无限图族$H$，它们具有这样的性质。 此外，我们证明如果输入图$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. 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.