algorithm - 以最少的步数销毁图形

Question

有一个有 N 个顶点和 M 个边的有向无环图。目的是破坏图形 - 通过以最少的步数删除其所有顶点。

---

一步删除规则：

1. 最多可以删除 2 个顶点。
2. 一个顶点只有在没有从它到任何未删除顶点的边时才能被删除。
3. 如果在一个步骤中删除了两个顶点，则它们之间不能有边。

约束：N,M <= 10^6，并且图没有自环和循环。

标签： algorithmdata-structuresgraphgraph-theorydirected-graph

Answer 1

HAROLD N. GABOW 的“一种用于两处理器调度的几乎线性算法”为此提供了一种算法。pdf在这里。

其基本思想是将顶点排序为最少的层数（每一层是忽略约束1时可以同时删除的所有顶点），然后先从最高层删除顶点。

该论文提供了更多细节和最优性证明。

编辑

要了解调度与给定问题的关系，请考虑调度一组作业。每个作业对应一个顶点。作业的依赖关系对应于有向边。

约束 2/3 对应于说只有在所有依赖项都已调度后才能调度作业。

约束 1 对应于说一次只能调度两个作业（即双处理器调度系统）。