2

问题如下：给定一个 DAG 和一个 number 0 < p ≤ 1，返回最小基数的顶点集合，它至少断开p从源（即，没有传入弧）到汇（即，没有传出弧）的路径的一部分）。对于p = 1，问题等价于最小割。但是，对于 的其他值p，我不确定答案是什么。

我正在考虑的一种算法是首先计算 DAG 的最小割集，然后尝试对其进行修剪以满足标准。这本身很有趣，看看我们找到的子集是否实际上p是给定特定的最小割集。该算法的问题在于它是浪费的，因为它计算了许多我们在最终答案中不需要的节点，实际上，它首先解决了“更大”的问题。

任何指向这个问题的解决方案？对于某些最小切算法，我们是否可能将这个额外的约束作为提前停止的标准？

为了检查有多少路径被删除，假设我们已经为每个顶点建立了索引（如果需要，会保持更新），这样我们就知道有多少路径因为它们的删除而断开连接。请不要担心正在更新的索引的复杂性。最后一件事，在大小或任何方面对生成的组件没有任何限制。

4

2 回答 2

1

这是获得近似最佳解决方案的想法。

有一个集合覆盖的变体，我想称之为部分集合覆盖，其中我们有集合和元素，并且想要最小数量的集合，其并集包含元素的 p 分数。为了应用于这个问题，集合对应于节点，元素对应于最大路径。（是的，有太多的路径可以天真地做到这一点；见下文。）当且仅当节点包含在路径中时，集合才包含元素。

将部分集覆盖写成整数程序并不难。

minimize sum_{sets S} x_S
subject to
for all elements e, sum_{sets S containing e} x_S >= y_e
sum_{elements e} y_e >= p * number of elements
for all sets S, x_S in {0, 1}      # 1 if set S is chosen
for all elements e, y_e in [0, 1]  # 1 if element e is covered

该程序可以通过整数程序求解器求解。求解器出奇地好，尽管它们当然不能保证这种 NP-hard 集覆盖泛化的最佳解决方案。

在一个有趣的 DAG 中，当然有太多的路径需要列举。采样救援！由于很容易计算 DAG 中的最大路径，因此很容易随机均匀地对它们进行采样。采样一些路径并将它们用作整数程序中的元素。

权衡是路径越多，目标的估计越好，但求解整数规划的时间更差。Hoeffding 不等式为正确选择样本数量提供了一些提示。对于 n 个顶点，有 2^n 个可能的解。我们希望这些中的每一个的估计分数在某个 epsilon 内是准确的。Hoeffding 说，我们需要将样本数选择为 Theta(n/epsilon^2)，以便几乎在所有时间里，所有的估计都是近似正确的。我会计算出确切的常数，但我怀疑它实际上是否相关。

于 2015-09-21T13:24:18.653 回答
0

EDIT1：看到OP的更新后，此解决方案适用于一个源u和一个接收器v的情况。

EDIT2：这实际上是一种启发式方法，请参阅下面评论中的反例。

这是基于以下线程中提供的路径计数方法的 O(V+E) 解决方案（由 David Eisenstat 指出，谢谢）：

DAG 中两个节点之间的路径数

在第一阶段，我们将完全应用 stalker 建议的“向后”方法。在此阶段结束时，我们将获取并存储以下信息：

  • 对于每个顶点 i，从 i 到 v 的路径数 F(i, v)

  • F(u, v)，从源 u 到汇 v 的路径数。

在第二阶段，我们继续使用相同的方法：我们模拟算法，就好像问题是找到从 v 到 u 的“反向路径”。最后，我们得到：

  • 对于每个顶点 i，从 i 到 u 的反向路径的数量 B(i, u)。显然 B(i, u) = F(u, i)

  • B(v, u) 等于 F(u, v)。

在第三阶段，我们为每个顶点 i 计算 P(i) = F(u, i) * F(i, v)。很容易证明遍历 i 的 (u, v) 路径的数量是 P(i)。因此，删除顶点 i 会导致删除 P(i) 路径。

在第四阶段也是最后一个阶段，我们以贪婪的方式进行：移除具有最高 P(i) 的顶点，直到移除的路径总数超过 p*F(u, v)

整体算法为 O(V+E)，因为：

  • 根据参考帖子，前两个阶段是 O(V+E)。

  • 第三和第四阶段显然是 O(V)，因此 O(V+E)

于 2015-09-21T12:35:08.907 回答