如何找到面向图的最大非循环子图的2近似解？

Question

如何确定一个没有定向图循环的最大子图的问题的2近似解？如果子图包含具有相同属性的其他图形中的最大边数,则子图为"最大".

2近似意味着我们可以构建比最佳图形小2倍的图形.这是一个相当大的约束减少,应该导致相当愚蠢的算法 - 哇! - 结果只比精确解决方案差两倍.

[这是我最近通过的考试的一个问题.不再做作业了.]

Answer 1

将节点集划分为两个非空集A和B.考虑从A到B的边集和从B到A的边集.从较小的集中抛出边并保留较大集的边(任意打破关系).单独递归A和B.

结果图是非循环的,因为每个循环都会在循环节点在A和B之间分割时被破坏.我们抛出的总边集不会大于我们保留的边集总数,所以我们抛出了最多一半的边缘.

[注意:我认为你的意思是'最大',你的意思是'最大'."最大"图表通常表示没有符合条件的正确超集的图表.最大的非循环子图很容易构造而没有近似因子,只有在没有添加循环的情况下,才能将所有边一次添加到一个新图中.

它可以在 O(E) 时间内完成。令 A 为 {v_1}，B 为 {v_2, ... v_n}。您只需比较 v_1 的入度和出度并删除度数较小的边即可。对 A = {v_2} 和 B = {v_3, ..., v_n} 重复此操作，比较 v_2 与 v_1 的入度/出度（忽略边）。 (2认同)

Answer 2

Vijay Vazirani 的关于近似算法的书将此作为第一个练习题，为此他给出了一个非常明显的提示，我将在此处对其进行解释。

正确性和近似比率证明都是微不足道的。

编辑：实际上@Keith Randall 的解决方案只是一个变体，他将集合 A 中的节点从 1 编号到 |A| 和来自 |A| 的 B 中的节点 + 1 到 |A| + |B|，对于递归情况也类似。