6
$\begingroup$

We are given a set of comparisons of the form z[i] < z[j] for various i and j and an unknown permutation z of length n.

We can assume those are transitively closed, or compute the closure relatively quickly by Floyd-Warshall.

Is there an efficient algorithm to determine the number of permutations compatible with the known comparisons? We can of course backtrack our way to the answer, but this would be quite slow.

The constraint we have looks like a forest of DAGs. It seems that by carefully counting the ways in which it can be collapsed into a line, we might get to the answer more directly.

Improve this question
$\endgroup$
4
  • $\begingroup$ As @a3nm mentions this is intractable for many comparisons, but there is likely a $poly(n) 2^{poly(k)}$ algorithm for $k$ comparisons, which would be much faster than brute force for small $k$. $\endgroup$
    – Geoffrey Irving
    Commented Oct 14, 2022 at 19:10
  • 1
    $\begingroup$ I've also found out that simple Markov chain over the set of linear extensions can mix very quickly making it practical to sample for them. Given that I'm after the average number of inversions among extensions, this is perfect for me. $\endgroup$
    – Arthur B
    Commented Oct 14, 2022 at 21:20
  • 2
    $\begingroup$ Although #P hard, it can be approximated (has a PTAS) via convex volume estimation. $\endgroup$
    – mic
    Commented Oct 14, 2022 at 22:19
  • $\begingroup$ I understand it involves 🍭 $\endgroup$
    – Arthur B
    Commented Oct 16, 2022 at 6:23

1 Answer 1

Reset to default
12
$\begingroup$

As far as I can tell, your problem is equivalent to the following: given a partial order (represented by its comparability pairs, which forms a DAG), count how many linear extensions it has.

This problem is known to be #P-hard, see Brightwell and Winkler, "Counting Linear Extensions", Order, 1991. It is #P-hard even in quite restricted cases, e.g., https://arxiv.org/abs/1802.06312

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Perhaps it is useful to add that there are exceptions when considering restricted classes of partial orders. N-free posets (series-parallel partial orders) have a poly-time solution to count the number of linear extensions. $\endgroup$
    – ExpressionCoder
    Commented Nov 1, 2022 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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