在固定模式图的研究中，我们探讨了在$n$个顶点、$d$-退化宿主图中计数同态、子图同构和诱导子图同构的算法复杂性。Bressan（Algorithmica, 2021）首次提出了DAG树宽度的概念，并证明了使用动态规划可以高效地计数同态和诱导子图，且只需多项式空间。在本研究中，我们引入了一种新的图参数，称为DAG树深度，这使得在$d$-退化宿主图中仅用常量空间就能高效地进行计数的分治算法。Bera等（SODA, 2021）证明了当且仅当模式图不包含长度至少为六的诱导环时，其DAG树宽度为一。这一诱导小特征使得我们能设计出线性时间和线性空间的算法。
基于这一系列工作，我们推导出DAG树深度不超过二的图的诱导小特征，且只需常量空间。最近，Paul-Pena和Seshadhri（ICALP, 2025）证明了所有最多九个顶点的模式图可以在次二次时间内使用多项式空间计数。我们进一步证明，所有最多九个顶点的模式图可以在$O(n^3)$时间内，使用常量空间计数为诱导子图。此外，我们还证明了最多十一顶点的模式图可以在$O(n^2)$时间内，使用多项式空间计数。最后，我们提出了一种常量空间的算法来计数诱导子图，其运行时间与Bressan的算法相匹配。此外，当允许多项式空间时，同态、子图同构和诱导子图同构的计数速度可以超过Bressan的算法。我们还建立了与DAG树宽度和DAG树深度相关的其他多个结果，可能具有独立的研究价值。
博主点评： 本文通过引入DAG树深度这一新参数，极大地推动了在常量空间内对退化图的计数算法研究。该研究不仅提供了新的理论框架，也为实际应用中的图算法优化提供了宝贵的参考。此类算法的高效性在大规模图处理领域具有重要意义，值得深入探讨。