求一个图算法:如何让图开心？

Question

背景：

如下图所示，图的左边有一个无向图。顶点由S2的S1表示...S6，并且边由顶点之间的线段表示。每条边都有一个权重(边附近的数字)，可以是正的，也可以是负的。

定义:

在图中，如果一个简单的循环有奇数条负边，则称为冲突循环，如果一个偶数（或零）条负边，则称为一致循环。在下图的左侧，例如，该图有两个冲突循环（S1-S2-S3-S1和S2-S3-S4-S2），其他循环是一致的。如果一个图没有冲突循环，则称为快乐。

目标:

通过删除一些边来使图形满意，同时确保成本（删除边的权重的绝对值之和）最低。在下图中，例如，在移除边缘（红线段）后，没有冲突的循环。因此，图形变得快乐，并且成本仅为2。

Answer 1

我为这个问题写了一个求解器（名为“符号图平衡”）。它基于固定参数算法，如果只需要删除很少的边，该算法速度很快。该方法在论文“基于分隔符的符号图平衡数据约简”中描述。

Answer 2

这个问题是NP难的，通过从最大割减少。给定一个最大割的实例，将所有边权重乘以-1。这个问题的约束要求删除边以消除所有奇数循环，即我们需要找到最大权重二部子图。

这个问题实际上相当于2标签唯一标签覆盖问题。目标是将每个顶点着色为黑色或白色，以最小化（i）连接不同颜色顶点的正边（ii）连接相同颜色顶点的负边的总成本。删除所有这些边是原始问题的有效解决方案。相反，给定一组要删除的有效边，我们可以确定一个着色。我希望有一种基于半定规划的近似算法（松弛可以用于分支和定界）。

但是，除非您熟悉组合优化，否则我建议的算法是整数规划。如果我们删除edgee，则让x（e）为1，如果我们不删除edge，则让x（e）为0。

minimize sum_{edges e} cost(e) x(e)
subject to
for every simple cycle C with an odd number of negative edges,
    sum_{edges e in C} x(e) >= 1
for each edge e, x(e) in {0, 1}

求解器将完成大部分工作。问题是处理我写的指数数量的约束。最简单的做法是生成所有简单的循环，并给求解器整个程序。另一种可能性是用约束的子集求解最优性，测试解决方案是否真的有效，如果无效，则引入一个或多个缺失的约束。要做测试，尝试对未删除的子图进行双色处理，这样由正边连接的顶点具有相同的颜色，由负边连接的顶点具有不同的颜色。贪婪地着色；如果我们卡住了，那么就有一个奇怪的循环出错了。

更复杂的是，可以通过一种称为列生成的技术来解决编写的程序。