2
$\begingroup$

Suppose that we have an array $A$ of $n$ elements with some partial order known, e.g. for example as a $n\times n$ matrix containing $c_{ij} \in \{-1, 0, 1\}$ where $0$ represents unknown and $-1, 1$ represent $A_i < A_j$ and $A_i \geq A_j$ respectively.

Is there an efficient algorithm that counts the number of partitions of $A$ that respect the partial order? E.g. for the all-zero matrix (totally undefined partial order) it's simply $n!$ and for a matrix containing a total order it's simply $1$.

We can assume that the partial order does not contain contradictions, e.g. we won't have $A_i < A_i$ or some chain of comparisons that violates transitivity.

$\endgroup$
2
$\begingroup$

Brightwell and Winkler proved that this program is #P-complete in their paper Counting linear extensions. You can, however, estimate the number of linear extensions efficiently.

$\endgroup$
  • $\begingroup$ Not what I'd like to hear, but oh well. Good to know that what I'm looking for is called a 'linear extension'. Thanks for your answer. $\endgroup$ – orlp Jan 22 '18 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.