Publication details
Counting Linear Extensions: Parameterizations by Treewidth
| Authors | |
|---|---|
| Year of publication | 2016 |
| Type | Article in Proceedings |
| Conference | 24th Annual European Symposium on Algorithms, {ESA} 2016, August 22-24, 2016, Aarhus, Denmark |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.4230/LIPIcs.ESA.2016.39 |
| Field | Informatics |
| Keywords | treewidth; linear extensions |
| Description | 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 com- plexity 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 xed- parameter intractable parameterized by the treewidth of the cover graph. This resolves an open problem recently posed in the Dagstuhl seminar on Exact Al- gorithms. On the positive side we show that #LE becomes xed-parameter tractable parameterized by the treewidth of the incomparability graph. |