3

我正在尝试编写一种算法来计算输入图（无向且无自环）的边缘团覆盖数（覆盖所有边缘的最小团数）。我的想法是

  1. 使用Bron-Kerbosch算法计算所有最大团，以及
  2. 尝试其中任何 1,2,3,... 是否会覆盖所有边缘，直到我找到最小数量

那行得通吗？有人知道更好的方法吗？有标准算法吗？令我惊讶的是，我找不到任何这样的算法。我知道这个问题是 NP 难的，所以我不希望有一个快速的解决方案。

4

2 回答 2

2

我会像你现在一样收集最大派系（或者可能使用其他算法，如CaptainTrunky建议的那样），然后使用branch 和 bound。这不能保证加速，但通常会在“简单”实例上产生很大的加速。

尤其是：

  • 与其按照子集大小递增的顺序尝试所有最大团子集，不如选择一条边 uv 并在其上分支。这表示：
    • 对于每个包含 uv 的最大团 C：
      • 制作一个包含当前解决方案中所有派系的试探性新部分解决方案
      • 将 C 添加到此部分解决方案中
      • 创建一个包含当前子问题图的新子问题，但 C 中的所有顶点都折叠成一个顶点
      • 递归解决这个较小的子问题。
  • 跟踪迄今为止最好的完整解决方案。这是您的上限(UB)。您不需要继续处理任何已经达到此上限但仍然存在边的子问题；更好的解决方案已经存在！
  • 最好选择一个由尽可能少的派系覆盖的边缘来分支。在选择以什么顺序尝试这些派系时，首先尝试您认为可能是最好的（可能是最大的）。

这是一个提高修剪水平的下限的想法：

如果子图 G' 包含大小为 s 的独立集，那么您将需要至少 s 个团来覆盖 G'（因为没有团可以覆盖独立集中的两个或多个顶点）。计算最大可能的 IS 是 NP 困难的，因此在这里不切实际，但是您可以通过使用顶点覆盖的 2 近似来获得一个便宜的界限：只需继续选择一条边并丢弃两个顶点，直到没有边为止；如果你扔掉了 k 个边，那么剩下的就是一个在 k 范围内的 IS。

到目前为止，您可以将此 IS 的大小添加到解决方案中的集团总数中；如果它比当前的 UB 大，你可以中止这个子问题，因为我们知道进一步充实它不能产生比我们已经看到的更好的解决方案。

于 2018-03-07T19:41:37.670 回答
1

2 年前我正在研究类似的问题，但我从未见过任何标准的现有方法。我做了以下事情：

  1. 计算所有最大团。 就我而言， MACE比 Bron-Kerbosch 好得多。
  2. 构建一个约束满足问题，以确定覆盖图所需的最小团数。你可以使用SAT、Minizinc、MIP工具来做到这一点。选哪一个？这取决于你的技能、时间资源、环境和许多其他参数。如果我们谈论的是概念验证，我会坚持使用 Minizinc。

第二部分的一些细节。为每条边定义一组布尔变量，如果它的value == True，那么它被覆盖，否则，它不是。添加允许您仅针对每个团覆盖边缘集的约束。最后，添加每个clique对应的变量，如果== True，则已经使用，否则，则不是。最后，要求覆盖所有边缘并且使用的派系数量最少。

于 2018-03-07T06:59:17.740 回答