A faster tree-decomposition based algorithm for counting linear extensions

Kustaa Kangas, M. Koivisto, S. Salonen, Pilipczuk M. Paul C. (Toimittaja)

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Abstrakti

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.
Alkuperäiskielienglanti
Otsikko13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
ToimittajatChristophe Paul, Michal Pilipczuk
Sivumäärä13
JulkaisupaikkaDagstuhl
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Julkaisupäivä2019
Artikkeli no5
ISBN (elektroninen)978-3-95977-084-2
DOI - pysyväislinkit
TilaJulkaistu - 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Parameterized and Exact Computation - Helsinki, Suomi
Kesto: 20 elokuuta 201824 elokuuta 2018
Konferenssinumero: 13
http://algo2018.hiit.fi/ipec/

Julkaisusarja

NimiLeibniz International Proceedings in Informatics
Vuosikerta115
ISSN (elektroninen)1868-8969

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Siteeraa tätä