GANIAN, Robert, Sebastian ORDYNIAK, Eduard EIBEN and Kanga KUSTAA. Counting Linear Extensions: Parameterizations by Treewidth. In Piotr Sankowski and Christos D. Zaroliagis. 24th Annual European Symposium on Algorithms, {ESA} 2016, August 22-24, 2016, Aarhus, Denmark. Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. p. 1-18. ISBN 978-3-95977-015-6. doi:10.4230/LIPIcs.ESA.2016.39. 2016.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Counting Linear Extensions: Parameterizations by Treewidth
Authors GANIAN, Robert (203 Czech Republic, guarantor, belonging to the institution), Sebastian ORDYNIAK (40 Austria), Eduard EIBEN (703 Slovakia) and Kanga KUSTAA (246 Finland).
Edition Aarhus, Denmark, 24th Annual European Symposium on Algorithms, {ESA} 2016, August 22-24, 2016, Aarhus, Denmark, p. 1-18, 18 pp. 2016.
Publisher Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
RIV identification code RIV/00216224:14330/16:00093946
Organization unit Faculty of Informatics
ISBN 978-3-95977-015-6
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.ESA.2016.39
Keywords in English treewidth; linear extensions
Tags core_A, firank_A
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 27/4/2017 07:09.
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 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.
PrintDisplayed: 19/4/2024 05:05