有向无环图(DAG)最大公共子图的求解方案或近似算法咨询

DAG场景下的最大公共子图问题仍属于NP难问题，但由于有向无环自带的拓扑序特性，有大量针对性的优化求解方案，实际运行效率远高于普通无结构图的通用解法，具体分为精确求解和近似算法两类：

精确求解方案 #

• 拓扑排序降维匹配：先对G1、G2分别做拓扑排序，把子图同构的匹配约束转化为拓扑序下的序列匹配约束，避免普通图中环结构带来的组合爆炸。如果两个DAG都属于串并联DAG这类特殊结构，甚至可以在多项式时间内得到精确解。
• 拓扑序动态规划：适合单图节点数在1000以内的中小规模DAG求解，状态定义为dp[u][v]，表示G1中以u为根的子图、G2中以v为根的子图的最大匹配节点数，按照拓扑序从叶子节点往根节点递推计算，配合节点出入度预剪枝（出入度差距过大的节点对直接跳过），实际运行效率比普通图的回溯法高2~3个数量级。
• 整数线性规划建模：适合工业场景下小范围的精确求解，DAG的拓扑序约束可以大幅减少ILP模型的变量数和约束数，商用求解器的运行速度远快于普通图的ILP模型。

近似算法 #

• 贪婪匹配策略：按照节点度数、属性相似度（如果节点带标签）给所有节点对排序，优先匹配相似度最高的节点对，匹配完成后移除两个节点的邻接边，重复迭代直到没有可匹配的节点对，时间复杂度为O(n*m)（n、m分别为G1、G2的节点数），在稀疏DAG场景下通常可以达到0.6~0.8的最优解近似比。
• 拓扑感知图嵌入匹配：先对两个DAG的节点做结合拓扑序的嵌入编码，把节点匹配问题转化为向量相似度匹配问题，再通过贪心或者线性分配得到匹配结果，适合节点数10w以上的超大规模DAG，速度最快，近似比通常在0.5以上。
• 特殊结构限制近似：如果允许匹配的子图为路径、树这类特殊结构，有专门的多项式时间近似算法，比如最大公共有向路径的近似比可以接近1。

如果你的业务场景中DAG还有额外的属性约束（比如节点带固定标签、边有权重限制），可以基于上述方案进一步增加剪枝规则，运行效率还能得到更大提升。

内容的提问来源于stack exchange，提问作者Nick Skywalker