Algorithm to determine number of total orderings of a poset

Question

In a poset with relation $\geq$, is there an algorithm to find the number of total orderings of this poset? If there is, is it P or NP? Is it equivalent to finding the number of total orderings of only the set of incomparable pairs?

Answer 1

What you’re looking for is the complexity of counting the linear extensions of a poset. Brightwell and Winkler showed that the problem is #P-complete.

Creating a linear extension amounts to resolving all of the incomparabilites—but that requires avoiding violating transitivity. You have to honor all the original comparabilities and ensure that your new comparabilities don’t contradict one another.