{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T21:37:30Z","timestamp":1748468250318,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T00:00:00Z","timestamp":1570060800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T00:00:00Z","timestamp":1570060800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["276864","316771"],"award-info":[{"award-number":["276864","316771"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the problem of computing the number of linear extensions of a given<jats:italic>n<\/jats:italic>-element poset whose cover graph has treewidth<jats:italic>t<\/jats:italic>. We present an algorithm that runs in time<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\tilde{O}}(n^{t+3})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mover><mml:mi>O<\/mml:mi><mml:mo>~<\/mml:mo><\/mml:mover><mml:mrow><mml:mo>(<\/mml:mo><mml:msup><mml:mi>n<\/mml:mi><mml:mrow><mml:mi>t<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>3<\/mml:mn><\/mml:mrow><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for any constant<jats:italic>t<\/jats:italic>; the notation<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\tilde{O}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mover><mml:mi>O<\/mml:mi><mml:mo>~<\/mml:mo><\/mml:mover><\/mml:math><\/jats:alternatives><\/jats:inline-formula>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<jats:italic>n<\/jats:italic>and<jats:italic>t<\/jats:italic>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.<\/jats:p>","DOI":"10.1007\/s00453-019-00633-1","type":"journal-article","created":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T09:08:05Z","timestamp":1570093685000},"page":"2156-2173","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions"],"prefix":"10.1007","volume":"82","author":[{"given":"Kustaa","family":"Kangas","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9662-3605","authenticated-orcid":false,"given":"Mikko","family":"Koivisto","sequence":"additional","affiliation":[]},{"given":"Sami","family":"Salonen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,3]]},"reference":[{"key":"633_CR1","doi-asserted-by":"crossref","unstructured":"Abseher, M., Musliu, N., Woltran, S.: HTD: A free, open-source framework for (customized) tree decompositions and beyond. In: Proceedings of the 14th International Conference on Integration of AI and OR Techniques in Constraint Programming, volume 10335 of Lecture Notes in Computer Science, pp. 376\u2013386. Springer, Berlin (2017)","DOI":"10.1007\/978-3-319-59776-8_30"},{"key":"633_CR2","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1613\/jair.5312","volume":"58","author":"M Abseher","year":"2017","unstructured":"Abseher, M., Musliu, N., Woltran, S.: Improving the efficiency of dynamic programming on tree decompositions via machine learning. J. Artif. Intell. Res. 58, 829\u2013858 (2017)","journal-title":"J. Artif. Intell. Res."},{"issue":"2","key":"633_CR3","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"AV Aho","year":"1972","unstructured":"Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput. 1(2), 131\u2013137 (1972)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"633_CR4","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebr. Discr. 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebr. Discr."},{"issue":"1","key":"633_CR5","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF00383170","volume":"7","author":"MD Atkinson","year":"1990","unstructured":"Atkinson, M.D.: On computing the number of linear extensions of a tree. Order 7(1), 23\u201325 (1990)","journal-title":"Order"},{"key":"633_CR6","doi-asserted-by":"crossref","unstructured":"Banks, J., Garrabrant, S., Huber, M.L., Perizzolo, A.: Using TPA to count linear extensions. arXiv preprint arXiv:1010.4981 (2017)","DOI":"10.1016\/j.jda.2018.04.001"},{"key":"633_CR7","volume-title":"Nonserial Dynamic Programming","author":"U Bertel\u00e8","year":"1972","unstructured":"Bertel\u00e8, U., Brioschi, F.: Nonserial Dynamic Programming. Academic Press, New York (1972)"},{"issue":"6","key":"633_CR8","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"633_CR9","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.dam.2004.01.008","volume":"145","author":"HL Bodlaender","year":"2005","unstructured":"Bodlaender, H.L., Fomin, F.V.: Tree decompositions with small cost. Discrete Appl. Math. 145(2), 143\u2013154 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"633_CR10","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"issue":"3","key":"633_CR11","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF00383444","volume":"8","author":"G Brightwell","year":"1991","unstructured":"Brightwell, G., Winkler, P.: Counting linear extensions. Order 8(3), 225\u2013242 (1991)","journal-title":"Order"},{"issue":"1\u20132","key":"633_CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0004-3702(99)00059-4","volume":"113","author":"R Dechter","year":"1999","unstructured":"Dechter, R.: Bucket elimination: a unifying framework for reasoning. Artif. Intell. 113(1\u20132), 41\u201385 (1999)","journal-title":"Artif. Intell."},{"issue":"1","key":"633_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M Dyer","year":"1991","unstructured":"Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM 38(1), 1\u201317 (1991)","journal-title":"J. ACM"},{"issue":"4","key":"633_CR14","doi-asserted-by":"crossref","first-page":"1657","DOI":"10.1007\/s00453-018-0496-4","volume":"81","author":"E Eiben","year":"2019","unstructured":"Eiben, E., Ganian, R., Kangas, K., Ordyniak, S.: Counting linear extensions: parameterizations by treewidth. Algorithmica 81(4), 1657\u20131683 (2019)","journal-title":"Algorithmica"},{"issue":"3","key":"633_CR15","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1137\/070711761","volume":"39","author":"M F\u00fcrer","year":"2009","unstructured":"F\u00fcrer, M.: Faster integer multiplication. SIAM J. Comput. 39(3), 979\u20131005 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"633_CR16","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/1656274.1656278","volume":"11","author":"M Hall","year":"2009","unstructured":"Hall, M., Frank, E., Holmes, G., Pfahringer, B., Reutemann, P., Witten, I.H.: The WEKA data mining software: an update. SIGKDD Explor. Newsl. 11(1), 10\u201318 (2009)","journal-title":"SIGKDD Explor. Newsl."},{"key":"633_CR17","unstructured":"Hart, W.B.: Fast library for number theory: an introduction. In: Proceedings of the Third International Congress on Mathematical Software, pp. 88\u201391. Springer, Berlin (2010). http:\/\/flintlib.org"},{"key":"633_CR18","unstructured":"Kangas, K., Hankala, T., Niinim\u00e4ki, T., Koivisto, M.: Counting linear extensions of sparse posets. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, pp. 603\u2013609. IJCAI\/AAAI Press (2016)"},{"key":"633_CR19","unstructured":"Kangas, K., Koivisto, M., Salonen, S.: A faster tree-decomposition based algorithm for counting linear extensions. In: Proceedings of the 13th International Symposium on Parameterized and Exact Computation, IPEC 2018 (2018, to appear)"},{"issue":"2","key":"633_CR20","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0167-6377(82)90044-X","volume":"1","author":"RM Karp","year":"1982","unstructured":"Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Oper. Res. Lett. 1(2), 49\u201351 (1982)","journal-title":"Oper. Res. Lett."},{"key":"633_CR21","doi-asserted-by":"crossref","unstructured":"Koivisto, M.: An $$O^*(2^n)$$ algorithm for graph coloring and other partitioning problems via inclusion\u2013exclusion. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pp. 583\u2013590. IEEE Computer Society (2006)","DOI":"10.1109\/FOCS.2006.11"},{"issue":"4","key":"633_CR22","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/1538902.1538906","volume":"56","author":"K Leyton-Brown","year":"2009","unstructured":"Leyton-Brown, K., Nudelman, E., Shoham, Y.: Empirical hardness models: methodology and a case study on combinatorial auctions. J. ACM 56(4), 22 (2009)","journal-title":"J. ACM"},{"key":"633_CR23","unstructured":"Lukasiewicz, T., Martinez, M.V., Simari, G.I.: Probabilistic preference logic networks. In: Proceedings of the 21st European Conference on Artificial Intelligence, Volume 263 of Frontiers in Artificial Intelligence and Applications, pp. 561\u2013566. IOS Press (2014)"},{"key":"633_CR24","doi-asserted-by":"crossref","unstructured":"Mannila, H., Meek, C.: Global partial orders from sequential data. In: Proceedings of the Sixth International Conference on Knowledge Discovery and Data Mining, pp. 161\u2013168. ACM (2000)","DOI":"10.1145\/347090.347122"},{"key":"633_CR25","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-94-009-2639-4_4","volume-title":"Algorithms and Order","author":"RH M\u00f6hring","year":"1989","unstructured":"M\u00f6hring, R.H.: Computationally tractable classes of ordered sets. In: Rival, I. (ed.) Algorithms and Order, pp. 105\u2013193. Kluwer Academic Publishers, Dordrecht (1989)"},{"issue":"3","key":"633_CR26","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1137\/080715822","volume":"23","author":"J Morton","year":"2009","unstructured":"Morton, J., Pachter, L., Shiu, A., Sturmfels, B., Wienand, O.: Convex rank tests and semigraphoids. SIAM J. Discrete Math. 23(3), 1117\u20131134 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"633_CR27","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1613\/jair.5128","volume":"57","author":"CJ Muise","year":"2016","unstructured":"Muise, C.J., Beck, J.C., McIlraith, S.A.: Optimal partial-order plan relaxation via MaxSAT. J. Artif. Intell. Res. 57, 113\u2013149 (2016)","journal-title":"J. Artif. Intell. Res."},{"key":"633_CR28","first-page":"57:1","volume":"17","author":"T Niinim\u00e4ki","year":"2016","unstructured":"Niinim\u00e4ki, T., Parviainen, P., Koivisto, M.: Structure discovery in Bayesian networks by sampling partial orders. J. Mach. Learn. Res. 17, 57:1\u201357:47 (2016)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"633_CR29","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s00453-004-1100-7","volume":"40","author":"M Peczarski","year":"2004","unstructured":"Peczarski, M.: New results in minimum-comparison sorting. Algorithmica 40(2), 133\u2013145 (2004)","journal-title":"Algorithmica"},{"key":"633_CR30","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0065-2458(08)60520-3","volume":"15","author":"JR Rice","year":"1976","unstructured":"Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65\u2013118 (1976)","journal-title":"Adv. Comput."},{"key":"633_CR31","volume-title":"Combinatorial Mathematics, Volume\u00a014 of Carus Mathematical Monographs","author":"HJ Ryser","year":"1963","unstructured":"Ryser, H.J.: Combinatorial Mathematics, Volume\u00a014 of Carus Mathematical Monographs. The Mathematical Association of America, Washington (1963)"},{"key":"633_CR32","doi-asserted-by":"crossref","unstructured":"Talvitie, T., Kangas, K., Niinim\u00e4ki, T., Koivisto, M.: Counting linear extensions in practice: MCMC versus exponential Monte Carlo. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (2018)","DOI":"10.1609\/aaai.v32i1.11528"},{"key":"633_CR33","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/j.jsc.2012.06.004","volume":"50","author":"J van der Hoeven","year":"2013","unstructured":"van der Hoeven, J., Lecerf, G.: On the bit-complexity of sparse polynomial and series multiplication. J. Symb. Comput. 50, 227\u2013254 (2013)","journal-title":"J. Symb. Comput."},{"key":"633_CR34","unstructured":"Wallace, C.S., Korb, K.B., Dai, H.: Causal discovery via MML. In: Proceedings of the 13th International Conference on Machine Learning, pp. 516\u2013524. Morgan Kaufmann (1996)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00633-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00633-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00633-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T21:29:26Z","timestamp":1664573366000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00633-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,3]]},"references-count":34,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["633"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00633-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,10,3]]},"assertion":[{"value":"30 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}