边团覆盖算法
Edge clique cover algorithm
我正在尝试编写一种算法来计算输入图（无向且无自循环）的边团覆盖数（覆盖所有边的最小团数）。我的想法是
- 使用 Bron-Kerbosch 算法计算所有最大派系，
- 尝试是否有任何 1,2,3,... 可以覆盖所有边缘，直到我找到
最小数量
那行得通吗，有没有人知道更好的方法；有标准算法吗？令我惊讶的是，我找不到任何这样的算法。我知道这个问题是 NP-hard，所以我不希望有一个快速的解决方案。
我在 2 年前研究过类似的问题，但我从未见过任何 标准 的现有方法。我做了以下事情：
- 计算所有最大派系。
MACE 比
Bron-Kerbosch 就我而言。
- 构建一个 constraint-satisfaction 问题来确定覆盖图形所需的 最小派系数 。您可以使用 SAT, Minizinc, MIP 工具来做到这一点。选择哪一个？这取决于您的技能、时间资源、环境和许多其他参数。如果我们谈论 proof-of-concept，我会坚持使用 Minizinc。
第二部分的一些细节。针对每条边定义一组布尔变量，如果value == True，则覆盖，否则不覆盖。添加约束，允许您仅针对每个集团覆盖边集。最后，添加每个clique对应的变量，如果== True，那么它已经被使用，否则，它不是。最后，要求覆盖所有边并且使用的团数最少。
我会像你现在做的那样收集最大的派系（或者可能使用不同的算法，如 ), but then use branch and bound 所建议的那样）。这不能保证加速，但通常会在 "easy" 实例。
特别是：
- 不是以递增的子集大小顺序尝试最大派系的所有子集，而是选择一个边 uv 并在其上分支。这表示：
- 对于每个包含 uv 的最大团 C：
- 制作一个新的部分解决方案，其中包含当前解决方案中的所有派系
- 将 C 添加到此部分解决方案
- 创建一个包含当前子问题图的新子问题，但 C 中的所有顶点都折叠成一个顶点
- 递归解决这个较小的子问题。
- 跟踪迄今为止最好的完整解决方案。这是您的 上限 (UB)。您不需要继续处理任何已经达到此上限但仍存在边的子问题；已经有更好的解决方案！
- 最好选择被尽可能少的派系覆盖的边缘作为分支。 When choosing in what order to try those cliques, try whichever you think is likely to be the best (probably the largest one) first.
这里有一个提高剪枝级别的下限想法：
如果子图 G' 包含大小为 s 的 independent set，那么您至少需要 s 个团来覆盖 G'（因为没有团可以覆盖独立集中的两个或多个顶点）。计算最大可能的 IS 是 NP-hard，因此在这里不切实际，但是您可以通过使用 Vertex Cover 的 2-approximation 获得一个便宜的边界：只需继续选择一条边并丢弃两个顶点，直到没有边为止；如果你扔掉了 k 条边，那么剩下的就是一个在最优 k 范围内的 IS。
到目前为止，您可以将此 IS 的大小添加到解决方案中的派系总数；如果它比当前的 UB 大，您可以中止这个子问题，因为我们知道进一步充实它不能产生比我们已经看到的更好的解决方案。
我正在尝试编写一种算法来计算输入图（无向且无自循环）的边团覆盖数（覆盖所有边的最小团数）。我的想法是
- 使用 Bron-Kerbosch 算法计算所有最大派系，
- 尝试是否有任何 1,2,3,... 可以覆盖所有边缘，直到我找到 最小数量
那行得通吗，有没有人知道更好的方法；有标准算法吗？令我惊讶的是，我找不到任何这样的算法。我知道这个问题是 NP-hard，所以我不希望有一个快速的解决方案。
我在 2 年前研究过类似的问题，但我从未见过任何 标准 的现有方法。我做了以下事情：
- 计算所有最大派系。 MACE 比 Bron-Kerbosch 就我而言。
- 构建一个 constraint-satisfaction 问题来确定覆盖图形所需的 最小派系数 。您可以使用 SAT, Minizinc, MIP 工具来做到这一点。选择哪一个？这取决于您的技能、时间资源、环境和许多其他参数。如果我们谈论 proof-of-concept，我会坚持使用 Minizinc。
第二部分的一些细节。针对每条边定义一组布尔变量，如果value == True，则覆盖，否则不覆盖。添加约束，允许您仅针对每个集团覆盖边集。最后，添加每个clique对应的变量，如果== True，那么它已经被使用，否则，它不是。最后，要求覆盖所有边并且使用的团数最少。
我会像你现在做的那样收集最大的派系（或者可能使用不同的算法，如
特别是：
- 不是以递增的子集大小顺序尝试最大派系的所有子集，而是选择一个边 uv 并在其上分支。这表示：
- 对于每个包含 uv 的最大团 C：
- 制作一个新的部分解决方案，其中包含当前解决方案中的所有派系
- 将 C 添加到此部分解决方案
- 创建一个包含当前子问题图的新子问题，但 C 中的所有顶点都折叠成一个顶点
- 递归解决这个较小的子问题。
- 对于每个包含 uv 的最大团 C：
- 跟踪迄今为止最好的完整解决方案。这是您的 上限 (UB)。您不需要继续处理任何已经达到此上限但仍存在边的子问题；已经有更好的解决方案！
- 最好选择被尽可能少的派系覆盖的边缘作为分支。 When choosing in what order to try those cliques, try whichever you think is likely to be the best (probably the largest one) first.
这里有一个提高剪枝级别的下限想法：
如果子图 G' 包含大小为 s 的 independent set，那么您至少需要 s 个团来覆盖 G'（因为没有团可以覆盖独立集中的两个或多个顶点）。计算最大可能的 IS 是 NP-hard，因此在这里不切实际，但是您可以通过使用 Vertex Cover 的 2-approximation 获得一个便宜的边界：只需继续选择一条边并丢弃两个顶点，直到没有边为止；如果你扔掉了 k 条边，那么剩下的就是一个在最优 k 范围内的 IS。
到目前为止，您可以将此 IS 的大小添加到解决方案中的派系总数；如果它比当前的 UB 大，您可以中止这个子问题，因为我们知道进一步充实它不能产生比我们已经看到的更好的解决方案。