Subgraph isomorphism problem

子圖同構問題：（Subgraph isomorphism problem（英语：Subgraph isomorphism problem）） 子集合加總問題 分團問題 頂點覆盖問題：（Vertex cover（英语：Vertex cover）） 獨立頂點集問題：（Independent set problem（英语：Independent

当所给的数据并非图的精确观测而是被随机误差污染时，更常用该约化形式并予以近似求解。另有与两个问题相关的更进一步的问题： 子图同构(Subgraph Isomorphism)问题：给定图 G {\displaystyle G} 和图 H {\displaystyle H} ，图 G {\displaystyle

Pachocki, J.; Socała, A. Tight bounds for graph homomorphism and subgraph isomorphism [圖同態與子圖同構之緊限界]. 28th Annual ACM-SIAM Symposium on Discrete Algorithms