Faster polynomial-space algorithms for poset problems
Source: arxiv.org/abs/2611.23653
We give a polynomial-space, deterministic, exact algorithm for counting linear extensions of partial orders over $n$ elements, with running time $O^*((2\sqrt{2})^{n}) \subseteq O(2.829^n)$. This improves upon the long-standing bound of $O^*(4^{n})$ attainable by standard divide and conquer (Savitch 1970, Gurevich and Shelah 1987). Our algorithm uses a similar balanced splitting approach as the classical algorithm, but applies it only to the elements outside a largest antichain. For the elements of the antichain itself we develop a formula based on inclusion-exclusion that accounts for the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.23653
curl -X POST /api/v1/records/arxiv/2611.23653/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.23653/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'