min未切割和min-csp_xor之间的等价

Question

在本文中

agarwal，amit等。 “o（√log n）分钟未切割，最小2cnf删除和定向切割问题的近似算法。”第三十七年度ACM ACM讨论会关于计算理论的载体。 2005。

agarwal等。声明以下两个问题是等同的。

考虑布尔变量 $ b_1，\ dots，b_n $ 形式 $ b_i \ oplus的一组约束b_j= 0 $ 和 $ b_i \ oplus b_j= 1 $ 。目标是最小化不满足的约束的数量。

和

给定图 $ g=（v，e）$ 查找剪切，最小化未切割边缘的数量。

如果约束只有 $ b_i \ oplus b_j= 1 $ ，则等价是简单的。但是，如果我们也考虑表单 $ b_i \ oplus b_j= 0 $ 的约束，则第一个配方似乎更普遍。

如何等效？

Answer 1

假设我们给出了一组形式 $ b_i \ oplus b_j= c $ 的约束。我们构造一个与一个顶点对应于每个 $ b_i $ 的一个图表。对于表单 $ b_i \ oplus b_j= 1 $ ，我们添加边缘 $ \ {i，j \ $ 。对于表单 $ b_i \ oplus b_j= 0 $ 的每个约束，我们添加一个新的顶点 $ x $ 和两个边缘 $ \ {i，x \}，\ {j，x \} $ 。

我们可以将切割作为顶点的分区分为两部分。对于表单 $ b_i \ oplus b_j= 1 $ ，约束是unslatfied iff $ i，j $ < / span>属于同一部分IFF $ \ {i，j \} $ 是未切割的。对于表单 $ b_i \ oplus b_j= 0 $ ，有两个案例：

• 如果约束是不满足的，则 $ i，j $ 属于不同的部分，所以究竟是一个边缘 $ \ {i，x \}，\ {j，x} $ 是未切割的。

• 如果约束不符合不满意，则 $ i，j $ 属于同一部分，因此（取决于 $ x $ ）零或两个边缘 $ \ {i，x}，\ {j，x \} $ < / span>未切割。由于我们旨在最大限度地减少未切割边缘的数量，因此我们可以假设零是未切割的。

总共，不满足的约束的数量与未切割边缘的数量相同。