Counting Linear Extensions of Sparse Posets / 603
Kustaa Kangas, Teemu Hankala, Teppo Niinimäki, Mikko Koivisto

We present two algorithms for computing the number of linear extensions of a given n-element poset. Our first approach builds upon an O(2n n)-time dynamic programming algorithm by splitting subproblems into connected components and recursing on them independently. The recursion may run over two alternative subproblem spaces, and we provide heuristics for choosing the more efficient one. Our second algorithm is based on variable elimination via inclusion-exclusion and runs in time O(nt+4)), where t is the treewidth of the cover graph. We demonstrate experimentally that these new algorithms outperform previously suggested ones for a wide range of posets, in particular when the posets are sparse.

PDF