Two-Processor Scheduling 学习笔记

为什么有人联考放论文题啊？不过好有趣。参考的 glx 博客。

考虑这么一个问题，给定一张偏序图，即一个满足传递性和非自反性的偏序关系 \(\succ\) 连成的 DAG。你需要对这张图进行拓扑排序，每次可以同时删去一个或者两个零入度点，问最少删多少次可以把图删空并构造方案。

形式化地说，我们需要求出两个等长序列 \(a,b\)，满足 \(\forall i>j,a_i/a_i \not\succ a_j/b_j\) 以及 \(a_i \not\succ b_i,b_i \not\succ a_i\)，然后最小化这个序列的长度。这里 \(b_i\) 可以取空点 \(\emptyset\)。

先考虑怎么玩出答案，首先我们可以得到一些答案的下界。比如我们建一张图 \(G\)，如果 \(x \not\succ b_i,b_i \not\succ y\) 即 \(x,y\) 互不可达，我们就连一条边。那么删图 \(G\) 的最大匹配一定能导出一个下界，因为同时删去的点只能取 \(G\) 中的一条边。事实上这似乎就是答案，然而一方面一般图最大匹配太难求，另一方面这个东西无法直接导出方案，毕竟删 \(G\) 中的边不能保证都是零入度点。

我们考虑一些更松的上界，对于 \(G\) 中的每一个联通块我们求它的大小除以二上取整的和，显然这是最大匹配的一个上界，也就是答案的下界，记为 \(F(G)\)。我们考虑再在 \(G\) 中删去一些点得到 \(G'\)，你会发现 \(F(G')\) 有可能比 \(F(G)\) 还大，这也说明在 \(G\) 中删去一些点之后反而有可能得到一个更紧的下界。我们可以说明我们可以通过这种方式直接让这个下界等于答案并同时给出一个顶到下界的构造。

咕咕。