题目大意

给定一张有向无环图$G$, 求最长反链长大小

反链的定义为一个点集$S$, 其中任意点对$(i,j)$ $(i \neq j)$ 既不存在$i$到$j$的路径, 也不存在$j$到$i$的路径

最长反链是$|S|$最大的的反链

Solution

根据CGL第一零零八六定理

最长反链的大小 $=$ 有向无环图最小路径可重复点覆盖

证明:

我们对$G$进行传递闭包, 得到的新图记为$G'$

问题转化为证明$G'$的最小路径点覆盖(路径不可重叠)为最长反链的大小

?藏身点集合为$H$, 路径集合为$P$, 显然, 每个路径中最多选取一个点, 所以$|P| \geq |H|$

接下来, 尝试构造一种情况使得$|P| = |H|$

?$G_2'$ 为$G'$ 的拆点二分图, 对于左侧非匹配点$x_{out}$, 说明这个点是路径的终点, 反复横跳后找到该路径的起点

?$E$ to denote that the set of the end point. For each of them, we label all the point that current point can arrive, and denote as $Nex$.

If $E \bigcap Nex = \emptyset $, $E$ is the answer we expected.

else we consider each point p in $E \bigcap Nex$, move along the path until current point $p' \notin Nex$, then remove $p$ from $E$ and add $p'$ to $E$.

and repeat with new $E$ until the condition is satisfied.

We can prove that we can find a legal $p'$ in any time when the condition is not satisfied.

Assumed that we can not find that $p'$, there must exsit a point $q$ that can arrive whole path where includes $p$. And it also means that the $P$ is not satisfied with the minimality which contradict with the premise.