A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

Show full item record




Kangas , K , Koivisto , M & Salonen , S 2020 , ' 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

Title: A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions
Author: Kangas, Kustaa; Koivisto, Mikko; Salonen, Sami
Contributor organization: Department of Computer Science
Date: 2020
Language: eng
Number of pages: 18
Belongs to series: Algorithmica
ISSN: 1432-0541
DOI: https://doi.org/10.1007/s00453-019-00633-1
URI: http://hdl.handle.net/10138/321138
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.
Subject: Algorithm selection
Empirical hardness
Linear extension
Multiplication of polynomials
Tree decomposition
113 Computer and information sciences
111 Mathematics
Peer reviewed: Yes
Rights: cc_by
Usage restriction: openAccess
Self-archived version: publishedVersion

Files in this item

Total number of downloads: Loading...

Files Size Format View
Kangas2020_Arti ... ree_DecompositionBased.pdf 349.2Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record