Counting Linear Extensions: Parameterizations by Treewidth

Eduard Eiben, Robert Ganian, Kustaa Kangas, Sebastian Ordyniak

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the #P-complete problem of counting the number of linear extensions of a poset (#LE); a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of #LE parameterized by the well-known decompositional parameter treewidth for two natural graphical representations of the input poset, i.e., the cover and the incomparability graph. Our main result shows that #LE is fixed-parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact Algorithms. On the positive side we show that #LE becomes fixed-parameter tractable parameterized by the treewidth of the incomparability graph.
Original languageEnglish
Pages (from-to)1657-1683
Number of pages27
JournalAlgorithmica
Volume81
Early online date4 Sept 2018
DOIs
Publication statusPublished - 1 Apr 2019

Cite this