Informace o publikaci
Counting Linear Extensions: Parameterizations by Treewidth
| Autoři | |
|---|---|
| Rok publikování | 2016 |
| Druh | Článek ve sborníku |
| Konference | 24th Annual European Symposium on Algorithms, {ESA} 2016, August 22-24, 2016, Aarhus, Denmark |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.4230/LIPIcs.ESA.2016.39 |
| Obor | Informatika |
| Klíčová slova | treewidth; linear extensions |
| Popis | 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. |