2026-08-06T00:20:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10206 2024-03-06T10:44:15Z ddc:004 open_access

A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions Kangas, Kustaa Koivisto, Mikko Salonen, Sami Algorithm selection empirical hardness linear extension multiplication of polynomials tree decomposition We consider the problem of counting the linear extensions of an n-element poset whose cover graph has treewidth at most t. We show that the problem can be solved in time O~(n^{t+3}), where O~ suppresses logarithmic factors. Our algorithm is based on fast multiplication of multivariate polynomials, and so differs radically from a previous O~(n^{t+4})-time inclusion - exclusion algorithm. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters n and t alone, fixing of which leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. For selecting an efficient tree decomposition we adopt the method of empirical hardness models, and show that it typically enables picking a tree decomposition that is significantly more efficient than a random optimal-width tree decomposition. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kustaa Kangas and Mikko Koivisto and Sami Salonen 2019 Is Part Of LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2018.5 urn:nbn:de:0030-drops-102062 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.5 eng https://creativecommons.org/licenses/by/3.0/legalcode