EIBEN, Eduard, Robert GANIAN, Kustaa KANGAS and Sebastian ORDYNIAK. Counting Linear Extensions: Parameterizations by Treewidth. Algorithmica. Springer, 2019, vol. 81, No 4, p. 1657-1683. ISSN 0178-4617. Available from: https://dx.doi.org/10.1007/s00453-018-0496-4.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Counting Linear Extensions: Parameterizations by Treewidth
Authors EIBEN, Eduard (703 Slovakia), Robert GANIAN (203 Czech Republic, guarantor, belonging to the institution), Kustaa KANGAS (246 Finland) and Sebastian ORDYNIAK (276 Germany).
Edition Algorithmica, Springer, 2019, 0178-4617.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher United States of America
Confidentiality degree is not subject to a state or trade secret
WWW URL
Impact factor Impact factor: 0.650
RIV identification code RIV/00216224:14330/19:00113714
Organization unit Faculty of Informatics
Doi http://dx.doi.org/10.1007/s00453-018-0496-4
UT WoS 000465431800013
Keywords in English Parameterized Complexity
Changed by Changed by: Mgr. Michal Petr, učo 65024. Changed: 14/5/2020 10:41.
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.
PrintDisplayed: 5/9/2024 01:24