algorithm - 寻找图的集团覆盖

Question

假设有一个黑匣子（/算法），它给了我一个图的集团。反正有没有从中找到派系的封面？

图片中给出了我想要找到的直观想法。我正在尝试找到黑匣子部分。如果需要进一步说明，请随意。我有一个想法，通过删除派系的边缘来更新图形。我不知道它会有多好。期待任何其他想法。

此外，如果您能给我提供任何关于近似团覆盖算法的良好参考，那将非常有帮助。

Answer 1

http://mathworld.wolfram.com/CliqueCoveringNumber.html

删除边对您没有帮助，因为新图可能缺少一个用于解决覆盖问题的集团。

    B
  / | \
A   |  D
  \ | /
    C

您有 2 个最大派系，ABC 和 BCD，如果您从 ABC 开始并删除它的边缘 AB AC 和 BC，您的算法将无法找到 BCD 派系。

---

在尝试计算团覆盖数之前，您需要图表的所有最大团。

AllCliques = GetAllCliques()
MaximalCliques = AllCliques
For Each ckA in MaximalCliques
  For Each ckB in MaximalCliques.Excluding(ckA)
    If all vertices in ckA are in ckB Then MaximalCliques.Remove(ckA)
    If all vertices in ckB are in ckA Then MaximalCliques.Remove(ckB)
Return MaximalCliques

然后从所有最大团中找到团覆盖数的天真方法通过排列并检查

MinCover = MaximalCliques.Count
For Each ckList in Permute(MaximalCliques)
  Cover = 0
  TestSet = Graph.Vertices
  For Each ck in ckList
    TestSet.Remove(ck.Vertices)
    Cover = Cover + 1
    If TestSet.Count = 0 Then Break
  If Cover < MinCover Then MinCover = Cover
Return MinCover