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'将被连接。
请再次查看任务描述并提供更多详细信息，(或将此示例作为反例以表明它可能无法解决)