A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2020-08-01
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
Algorithmica
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 O~ (nt + 3) for any constant t; the notation 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.Description
Keywords
Algorithm selection, Empirical hardness, Linear extension, Multiplication of polynomials, Tree decomposition
Other note
Citation
Kangas , K , Koivisto , M & Salonen , S 2020 , ' A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions ' , Algorithmica , vol. 82 , no. 8 , pp. 2156-2173 . https://doi.org/10.1007/s00453-019-00633-1