algorithm - 从偏序的线性扩展传递减少

Question

是否有一种有效的算法可以从偏序的单个线性扩展创建传递减少？

更新：实际上，部分顺序是已知的。我也知道计算给定偏序的传递减少的时间复杂度。我想知道的是：给定一个偏序及其线性扩展之一，可以降低时间复杂度吗？

Answer 1

渐近地说，答案是否定的。只需检查整个输入，就有一个微不足道的 Omega(n + m) 下限，并且拓扑排序在时间 O(n + m) 上产生线性扩展，这不会为任何正确的算法增加渐近成本。

Answer 2

如果我理解正确的问题，部分排序的线性扩展可以通过在输入的编码长度中使用时间线性的拓扑排序来生成。按照您问题中的链接，生成的序列已经是其自身的传递缩减，因为它的传递闭包是相同的可达性关系。但是，请注意，初始偏序的线性扩展可能不是唯一确定的。