{"id":"arxiv/2611.23653","url":"https://arxiv.org/abs/2611.23653","tags":["cs.DS","math.CO"],"score":0,"title":"Faster polynomial-space algorithms for poset problems","domain":"cs.DS","source":"arxiv","authors":["László Kozma","Junqi Tan"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-18","reactions":{}}