问题给出如下:
给定一个 DAG 和一个数字 0 < p ≤ 1 , 返回断开至少 p 的顶点的最小基数集- 从源(即没有传入弧)到汇(即没有传出弧)的路径的分数。
对于 p = 1 ，这个问题相当于最小割。对于 p 的其他值，但是，我不确定答案是什么。
我正在考虑的一种算法是首先计算 DAG 的最小割集，然后尝试对其进行修剪以满足条件。这本身很有趣，看看我们找到的子集是否实际上是特定 p 的最小割集。那是给定的。这个算法的问题是它很浪费，因为它计算了很多我们在最终答案中不需要的节点，实际上，它首先解决了“更大”的问题。
有解决这个问题的方法吗？有没有可能对于min-cut的一些算法，我们把这个额外的约束条件作为早停标准？
为了检查有多少条路径被移除，假设我们已经为每个顶点建立了索引(并在需要时保持更新)以便我们知道有多少条路径因它们的移除而断开连接。请不要担心正在更新的索引的复杂性。最后一件事，在大小或任何方面对生成的组件没有限制。
最佳答案
这里有一个获得近似最优解的想法。
有一个集合覆盖的变体，我想称之为部分集合覆盖，其中我们有集合和元素，并且想要最小数量的集合，其并集包含元素的 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's inequality给出了一些关于正确选择样本数量的提示。对于 n 个顶点，有 2^n 种可能的解决方案。我们希望每一个的估计分数都精确到某个 epsilon 以内。 Hoeffding 说我们需要将样本数选择为 Theta(n/epsilon^2)，这样几乎所有时间，所有估计都大致正确。我会计算出确切的常数，但我怀疑它是否实际相关。
关于algorithm - 在 DAG 中找到断开特定部分路径的最小顶点集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32693459/