A faster tree-decomposition based algorithm for counting linear extensions

Kustaa Kangas, M. Koivisto, S. Salonen, Pilipczuk M. Paul C. (Redaktör)

Forskningsoutput: Kapitel i bok/rapport/konferenshandlingKonferensbidragVetenskapligPeer review

Sammanfattning

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.
Originalspråkengelska
Titel på gästpublikation13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
RedaktörerChristophe Paul, Michal Pilipczuk
Antal sidor13
UtgivningsortDagstuhl
FörlagSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Utgivningsdatum2019
Artikelnummer5
ISBN (elektroniskt)978-3-95977-084-2
DOI
StatusPublicerad - 2019
MoE-publikationstypA4 Artikel i en konferenspublikation
EvenemangInternational Symposium on Parameterized and Exact Computation - Helsinki, Finland
Varaktighet: 20 aug 201824 aug 2018
Konferensnummer: 13
http://algo2018.hiit.fi/ipec/

Publikationsserier

NamnLeibniz International Proceedings in Informatics
Volym115
ISSN (elektroniskt)1868-8969

Vetenskapsgrenar

  • 113 Data- och informationsvetenskap

Citera det här