# A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

 dc.contributor University of Helsinki, Aalto University en dc.contributor University of Helsinki, Department of Computer Science en dc.contributor University of Helsinki, Department of Computer Science en dc.contributor.author Kangas, Kustaa dc.contributor.author Koivisto, Mikko dc.contributor.author Salonen, Sami dc.date.accessioned 2020-11-05T13:39:01Z dc.date.available 2020-11-05T13:39:01Z dc.date.issued 2019-10-03 dc.identifier.citation Kangas , K , Koivisto , M & Salonen , S 2019 , ' A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions ' , Algorithmica , vol. 82 , pp. 2156-2173 . https://doi.org/10.1007/s00453-019-00633-1 en dc.identifier.issn 1432-0541 dc.identifier.other PURE: 127371846 dc.identifier.other PURE UUID: 435f39bf-47cf-4883-b94f-caf56f87fc37 dc.identifier.other RIS: urn:B59D07B4061B2B7E089BD696AF49705F dc.identifier.other RIS: Kangas2019 dc.identifier.other ORCID: /0000-0001-9662-3605/work/83052281 dc.identifier.other ORCID: /0000-0002-5262-7919/work/83052834 dc.identifier.other WOS: 000557558900003 dc.identifier.uri http://hdl.handle.net/10138/321138 dc.description.abstract We investigate the problem of computing the number of linear extensions of a given n-element poset whose cover graph has treewidth t. We present an algorithm that runs in time $${\tilde{O}}(n^{t+3})$$O~(nt+3)for any constant t; the notation $${\tilde{O}}$$O~hides polylogarithmic factors. Our algorithm applies dynamic programming along a tree decomposition of the cover graph; the join nodes of the tree decomposition are handled by fast multiplication of multivariate polynomials. 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 these parameters leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. We compare two approaches to select an efficient tree decomposition: one is to include additional features of the tree decomposition to build a more accurate, heuristic cost function; the other approach is to fit a statistical regression model to collected running time data. Both approaches are shown to yield a tree decomposition that typically is significantly more efficient than a random optimal-width tree decomposition. en dc.format.extent 18 dc.language.iso eng dc.relation.ispartof Algorithmica dc.rights en dc.subject Algorithm selection en dc.subject COMPLEXITY en dc.subject Empirical hardness en dc.subject FRAMEWORK en dc.subject Linear extension en dc.subject Multiplication of polynomials en dc.subject Tree decomposition en dc.subject 113 Computer and information sciences en dc.subject 111 Mathematics en dc.title A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions en dc.type Article dc.description.version Peer reviewed dc.identifier.doi https://doi.org/10.1007/s00453-019-00633-1 dc.type.uri info:eu-repo/semantics/other dc.type.uri info:eu-repo/semantics/publishedVersion dc.contributor.pbl