Counting Linear Extensions of Sparse Posets

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

Counting Linear Extensions of Sparse Posets

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

Download BibTeX Cite

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.

Kustaa Kangas, Teemu Hankala, Teppo Mikael Niinimäki, and Mikko Koivisto. 2016. Counting Linear Extensions of Sparse Posets. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 603–608. https://ijcai.org/proceedings/2016/92

@inproceedings{ijcai2016p92,
  title     = {Counting Linear Extensions of Sparse Posets},
  author    = {Kangas, Kustaa and Hankala, Teemu and Niinimäki, Teppo Mikael and Koivisto, Mikko},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {603--608},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/92},
}

TY  - CPAPER
TI  - Counting Linear Extensions of Sparse Posets
AU  - Kangas, Kustaa
AU  - Hankala, Teemu
AU  - Niinimäki, Teppo Mikael
AU  - Koivisto, Mikko
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 603
EP  - 608
UR  - https://ijcai.org/proceedings/2016/92
ER  -