algorithm - 有向图划分为子图

Question

给定一个带有 |V| 的 DAG = n 并且有 s 个源，我们必须呈现子图，使得每个子图大约有 k1=√|s| 源和近似 k2=√|n| 节点。

如果我们将 DAG 的高度定义为从某个源到某个汇的最大路径长度。

我们要求生成的所有子图都具有大致相同的高度。

每对节点集（子图）的交集为空。

您可以在附图中看到右分区的示例（图中的每条边都指向上方）。

示例中有 36 个节点和 8 个接收器 [#10,11,12,13,20,21,22,23]。所以每个子图应该有 6 个节点和 2 或 3 个接收器。

你对算法有想法吗？

非常感谢

Answer 1

即使我们假设图表是间接连接的，您似乎也错过了一些信息。看下面的例子。
您应该在每个子图中有 3 个顶点，但是，请查看顶点 6，如果没有 5 - 我们就完成了，因为该图没有连接，就像您在评论中所说的那样。
如果是 - 最多只能是 {7,8,9} 之一 - 假设它是 7。即 U={5,6,7}
现在让我们看一下 8，假设它在 U' 中，因为5 不在 U' 中，没有可能的解决方案，其中子集 U' 将被连接。
请再次查看任务描述并提供更多详细信息，（或将此示例作为反例以表明它可能无法解决）