A faster tree-decomposition based algorithm for counting linear extensions

• Main Authors: Kangas, Kustaa, Koivisto, M., Salonen, S.
• Other Authors: Paul, Christophe, Pilipczuk, Michal, Doctoral Programme in Computer Science, Department of Computer Science, University Management
• Format: Conference Object
• Language: English
• Published: 2021
• Subjects: Parameter estimation; Counting linear extensions; Cover graph; Exclusion algorithms; Fast multiplication; Linear extensions; Multivariate polynomial; Running time; Tree decomposition; Trees (mathematics); 113 Computer and information sciences; Kangas; Koivisto; sami
• Online Access: http://hdl.handle.net/10138/325877

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 Õ(nt+3), where Õ suppresses logarithmic factors. Our algorithm is based on fast multiplication of multivariate polynomials, and so differs radically from a previous Õ(nt+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. © Kustaa Kangas, Mikko Koivisto, and Sami Salonen; licensed under Creative Commons License CC-BY. Peer reviewed