如何找到两个图的最大公共子图？

Question

嗨，我需要帮助寻找图形算法

我正在研究与距离函数相关的以下方程

d (g1, g2)   = 1-       ?mcs(g1,g2) ?  /
             ?g1?+?g2?-?mcs (g1, g2) ?

在哪里

• d (g1,g2) : 是基于最大公共子图的距离函数。
• g1, g2 是两张图。
• mcs (g1,g2): 是两个图 g1,g2 的最大公共子图，其中 mcs 是两个主题图中包含的最大图（通过某种涉及节点和边数的度量）。
• ?g1?：共同诱导子图g1的基数
• ?g2?：共同诱导子图g2的基数

我的问题：如何计算 MCS？
我在互联网上搜索过，但大多数算法都很复杂，任何人都知道从哪里可以得到一个简单的算法来在 matlab 中编程这个方程。

Answer 1

问题是NP-Complete ¹。

从Clique 问题²的减少。给定一个集团问题的实例——一个图G=(V,E)，创建一个完整的集团 G'=(V,E')，使得E' = {(u,v) | u != v, for each u,v in V)。

极大团问题的解与 G 和 G' 的极大子图问题的解相同。由于集团问题是 NP-Hard，所以这个问题也是。

因此，这个问题没有已知的多项式解。

如果您正在寻找精确算法，您可以尝试穷举搜索方法和/或分支定界方法来解决它。对于坏消息很抱歉，但至少你知道不要寻找（可能）不存在的东西（当然，除非P=NP）

编辑：问题的指数蛮力解决方案：
您可以检查所有可能的子集，并检查它是否是可行的解决方案。
伪代码：

findMCS(vertices,G1,G2,currentSubset):
  if vertices is empty: //base clause, no more candidates to check
      if isCommonSubgraph(G1,G2,currentSubset):
         return clone(currentSubset)
      else:
         return {}
  v <- vertices.pop() //take a look at the first element
  cand1 <- findMCS(vertices,G1,G2,currentSubset) //find MCS if it is NOT in the subset
  currentSubset.append(v)
  if isCommonSubgrah(G1,G2,currentSubset): //find MCS if it is in the subset
     cand2 <- findMCS(vertices,G1,G2,currentSubset)
  currentSubset.remvoe(v) //clean up environment before getting back from recursive call
  return (|cand1| > |cand2| ? cand1 : cand2) //return the maximal subset from all candidates

上面的复杂性是O(2^n)（检查所有可能的子集），并使用：（findMCS(G1.vertices, G1, G2, [])其中[]是空列表）调用它。

笔记：

• isCommonSubgrah(G1,G2,currentSubset)是一种易于计算的方法，当且仅当currentSubset是 G1 和 G2 的公共子图时才回答真。
• |cand1| 和 |cand2| 是这些列表的大小。

(1) 假设最大子图是Uin的子集V，对于每个u1,u2inU (u1,u2)是 inE1当且仅当(u1,u2)in E2（直观地，两个图中共享完全相同边的顶点的最大子集）

(2) 集团问题：给定一个实例，G=(V,E)找到最大子集UinV使得对于每个u1,u2in U:u1 = u2或(u1,u2)is in E。