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

Question

有一个有向无环图，有N个顶点和M条边。目的是破坏图 - 通过在最小步数中删除所有顶点。

---

一步删除规则:

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

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

Answer 1

HAROLD N. GABOW 的“An Almost-Linear Algorithm for Two-Processor Scheduling”为此给出了算法。 pdf here .

基本思想是将顶点排序到最少的层数(每一层是如果我们忽略约束1可以同时删除的所有顶点)，然后从最高层开始删除顶点。

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

编辑

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

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

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