有向无环图有n个顶点和m个边。其目的是通过以最少的步骤删除图的所有顶点来破坏图。
一步删除规则：
最多可以删除2个顶点。
只有当顶点与任何未删除的顶点之间没有边时，才能删除该顶点。
如果一步删除两个顶点，则它们之间不能有边。
约束条件：n，m<=10^6，图没有自循环和循环。
最佳答案
HAROLD N.GABOW的“两处理器调度的近似线性算法”给出了一个算法pdf here。
其基本思想是将顶点排序到最小级别（每个级别是忽略约束1时可以同时删除的所有顶点），然后先从最高级别删除顶点。
本文给出了最优性的更详细的证明。
编辑
要了解调度与给定问题的关系，请考虑调度一组作业每个作业对应一个顶点。作业的依赖项对应于定向边。
约束2/3对应于这样一种说法：一个作业只能在所有依赖项都被调度之后才被调度。
约束1对应于一次只能调度两个作业（即两个处理器调度系统）。