Counting Linear Extensions Faster than $2^n$
Keigo Oka
We give a deterministic algorithm that counts the linear extensions of any $n$-element poset in $O^*(33^{n/6}) \le O^*(1.791^n)$ time and space, breaking the $O^*(2^n)$ barrier of standard order-ideal dynamic programming without assumptions on height, width, or dimension. Our algorithm fixes an antichain $B$ and tracks order ideals only on the remaining core $V \setminus B$. For each element $v \in B$ that has successors in the core, we guess which of those successors appears first in the linear extension, reducing all upper constraints on $v$ to a single deadline. An element $v \in B$ becomes available once all of its core predecessors have been placed; available elements with the same deadline then face identical remaining constraints, so the dynamic program only needs to record how many available elements have each deadline and weight transitions by the number of choices for the next element. Taking $B$ to be a maximum antichain and balancing this dynamic program against a Dilworth chain partition yields an $O^*(1.89^n)$ algorithm. To obtain our main bound, we use a minimum-cut computation in an auxiliary bipartite network to find an antichain $B$ whose comparability neighborhood $R$ satisfies $|B| \ge 5|R|$ while the remainder $V \setminus (B \cup R)$ partitions into stars with at most five leaves. Since a $j$-leaf star has $2^j+1$ independent sets and $(2^j+1)^{1/(j+1)} \le 33^{1/6}$ for $1 \le j \le 5$, combining the star bound on the remainder with our state bound on $B \cup R$ gives $O^*(33^{n/6})$ time and space.
尚无 AI 解读，展示原文摘要