For any finite set $\mathcal{H} = \{H_1,\ldots,H_p\}$ of graphs, a graph is $\mathcal{H}$-subgraph-free if it does not contain any of $H_1,\ldots,H_p$ as a subgraph. We give a meta-classification for $\mathcal{H}$-subgraph-free graphs: assuming a problem meets some three conditions, then it is ``efficiently solvable'' if $\mathcal{H}$ contains a disjoint union of one or more paths and subdivided claws, and is ``computationally hard'' otherwise. The conditions are that the problem should be efficiently solvable on graphs of bounded treewidth, computationally hard on subcubic graphs, and computational hardness is preserved under edge subdivision. We illustrate the broad applicability of our meta-classification by obtaining a dichotomy between polynomial-time solvability and NP-completeness for many well-known partitioning, covering and packing problems, network design problems and width parameter problems. For other problems, we obtain a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). Along the way, we uncover and resolve several open questions from the literature, while adding many new ones.

翻译：对于任何有限集 $\mathcal{H} = \{H_1,\ldots,H_p\}$ 的图，如果它不包含 $H_1,\ldots,H_p$ 中的任意一个作为子图，则称该图为 $\mathcal{H}$-子图禁止的。我们给出了 $\mathcal{H}$-子图禁止图的元分类：假设问题满足某些三个条件，则如果 $\mathcal{H}$ 包含一个或多个路径的不交并和经过子爪，则它是“有效可解的”，否则它是“计算难度”的。这些条件是问题在有界树宽图上应该可以有效解决，在亚立方图上计算难，在边的细分下计算难度能得到维持。我们通过获得很多著名的分区、覆盖和打包问题的多项式可解性和 NP 完全性的二分法，网络设计问题和宽度参数问题。对于其他问题，我们获得了几乎线性时间可解性和没有子二次时间算法（在某些难度假设的情况下）之间的二分法。在这个过程中，我们揭示和解决了文献中的几个悬而未决的问题，并添加了许多新问题。