Eiben E, Ganian R, Kangas K, Ordyniak S
1Department of Informatics, University of Bergen, Bergen, Norway.
2Algorithms and Complexity Group, TU Wien, Vienna, Austria.
Algorithmica. 2019;81(4):1657-1683. doi: 10.1007/s00453-018-0496-4. Epub 2018 Sep 4.
We consider the -complete problem of counting the number of linear extensions of a poset ; a fundamental problem in order theory with applications in a variety of distinct areas. In particular, we study the complexity of 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 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 becomes fixed-parameter tractable parameterized by the treewidth of the incomparability graph.
我们考虑偏序集线性扩张数量计数的 - 完全问题；这是序理论中的一个基本问题，在多个不同领域都有应用。特别地，对于输入偏序集的两种自然图形表示，即覆盖图和不可比图，我们研究了以著名的分解参数树宽为参数的 的复杂度。我们的主要结果表明，以覆盖图的树宽为参数时， 是固定参数难处理的。这解决了最近在达格斯图尔精确算法研讨会上提出的一个开放问题。从积极的方面来看，我们表明以不可比图的树宽为参数时 的问题变得固定参数可处理。
