---
title: "Counting Linear Extensions of Sparse Posets"
authors:
  - "Kustaa Kangas"
  - "Teemu Hankala"
  - "Teppo Mikael Niinimäki"
  - "Mikko Koivisto"
doi: ""
url: "https://ijcai.org/proceedings/2016/92"
pdf: "https://ijcai.org/proceedings/2016/0092.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "603-608"
track: ""
keywords:
---

# Counting Linear Extensions of Sparse Posets

Kustaa Kangas, Teemu Hankala, Teppo Mikael Niinimäki, Mikko Koivisto

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 603-608.

## Abstract

We present two algorithms for computing the number of linear extensions of a given n-element poset. Our first approach builds upon an O(2n n)-time dynamic programming algorithm by splitting subproblems into connected components and recursing on them independently. The recursion may run over two alternative subproblem spaces, and we provide heuristics for choosing the more efficient one. Our second algorithm is based on variable elimination via inclusion-exclusion and runs in time O(nt+4)), where t is the treewidth of the cover graph. We demonstrate experimentally that these new algorithms outperform previously suggested ones for a wide range of posets, in particular when the posets are sparse.