Document Open Access Logo

A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

Authors Kustaa Kangas, Mikko Koivisto, Sami Salonen

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.5.pdf
  • Filesize: 487 kB
  • 13 pages

Document Identifiers

Author Details

Kustaa Kangas
  • Department of Computer Science, Aalto University, Espoo, Finland
Mikko Koivisto
  • Department of Computer Science, University of Helsinki, Helsinki, Finland
Sami Salonen
  • Department of Computer Science, University of Helsinki, Helsinki, Finland

Funding

This work was partially supported by the Academy of Finland, Grant 276864, "Supple Exponential Algorithms."

Cite As Get BibTex

Kustaa Kangas, Mikko Koivisto, and Sami Salonen. A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.5

Abstract

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 O~(n^{t+3}), where O~ suppresses logarithmic factors. Our algorithm is based on fast multiplication of multivariate polynomials, and so differs radically from a previous O~(n^{t+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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithm design techniques
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Algorithm selection
  • empirical hardness
  • linear extension
  • multiplication of polynomials
  • tree decomposition

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Michael Abseher, Nysret Musliu, and Stefan Woltran. 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, pages 376-386. Springer, 2017. Google Scholar
  2. Michael Abseher, Nysret Musliu, and Stefan Woltran. Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning. J. Artif. Intell. Res., 58:829-858, 2017. Google Scholar
  3. Alfred V. Aho, M. R. Garey, and Jeffrey D. Ullman. The Transitive Reduction of a Directed Graph. SIAM J. Comput., 1(2):131-137, 1972. Google Scholar
  4. Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of Finding Embeddings in a K-tree. SIAM J. Algebra. Discr., 8(2):277-284, April 1987. Google Scholar
  5. Mike D. Atkinson. On computing the number of linear extensions of a tree. Order, 7(1):23-25, 1990. Google Scholar
  6. Jacqueline Banks, Scott Garrabrant, Mark L. Huber, and Anne Perizzolo. Using TPA to count linear extensions. arXiv preprint arXiv:1010.4981, 2017. Google Scholar
  7. Umberto Bertelè and Francesco Brioschi. Nonserial Dynamic Programming. Academic Press, 1972. Google Scholar
  8. Hans L. Bodlaender. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. Google Scholar
  9. Hans L. Bodlaender and Fedor V. Fomin. Tree decompositions with small cost. Discrete Appl. Math., 145(2):143-154, 2005. Google Scholar
  10. Hans L. Bodlaender and Ton Kloks. Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs. J. Algorithms, 21(2):358-402, 1996. Google Scholar
  11. Graham Brightwell and Peter Winkler. Counting linear extensions. Order, 8(3):225-242, 1991. Google Scholar
  12. Rina Dechter. Bucket elimination: A unifying framework for reasoning. Artif. Intell., 113(1-2):41-85, 1999. Google Scholar
  13. Martin Dyer, Alan Frieze, and Ravi Kannan. A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies. J. ACM, 38(1):1-17, 1991. Google Scholar
  14. Eduard Eiben, Robert Ganian, Kustaa Kangas, and Sebastian Ordyniak. Counting Linear Extensions: Parameterizations by Treewidth. In Proceedings of the 24th Annual European Symposium on Algorithms, volume 57 of LIPIcs, pages 39:1-39:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  15. Mark Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, and Ian H. Witten. The WEKA Data Mining Software: An Update. SIGKDD Explor. Newsl., 11(1):10-18, November 2009. Google Scholar
  16. William B. Hart. Fast Library for Number Theory: An Introduction. In Proceedings of the Third International Congress on Mathematical Software, pages 88-91, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://flintlib.org.
  17. Kustaa Kangas, Teemu Hankala, Teppo Niinimäki, and Mikko Koivisto. Counting linear extensions of sparse posets. In Proceedings of the 25th International Joint Conference on Artificial Intelligence, pages 603-609. IJCAI/AAAI Press, 2016. Google Scholar
  18. Richard M. Karp. Dynamic Programming Meets the Principle of Inclusion and Exclusion. Oper. Res. Lett., 1(2):49-51, April 1982. Google Scholar
  19. Mikko Koivisto. An O^*(2ⁿ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion-Exclusion. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 583-590. IEEE Computer Society, 2006. Google Scholar
  20. Kevin Leyton-Brown, Eugene Nudelman, and Yoav Shoham. Empirical hardness models: Methodology and a case study on combinatorial auctions. J. ACM, 56(4), 2009. Google Scholar
  21. Thomas Lukasiewicz, Maria V. Martinez, and Gerardo I. Simari. Probabilistic Preference Logic Networks. In Proceedings of the 21st European Conference on Artificial Intelligence, volume 263 of Frontiers in Artificial Intelligence and Applications, pages 561-566. IOS Press, 2014. Google Scholar
  22. Heikki Mannila and Christopher Meek. Global Partial Orders from Sequential Data. In Proceedings of the Sixth International Conference on Knowledge Discovery and Data Mining, pages 161-168. ACM, 2000. Google Scholar
  23. Rolf H. Möhring. Computationally tractable classes of ordered sets. In I. Rival, editor, Algorithms and Order, pages 105-193. Kluwer Academic Publishers, 1989. Google Scholar
  24. Jason Morton, Lior Pachter, Anne Shiu, Bernd Sturmfels, and Oliver Wienand. Convex Rank Tests and Semigraphoids. SIAM J. Discrete Math., 23(3):1117-1134, 2009. Google Scholar
  25. Christian J. Muise, J. Christopher Beck, and Sheila A. McIlraith. Optimal Partial-Order Plan Relaxation via MaxSAT. J. Artif. Intell. Res., 57:113-149, 2016. Google Scholar
  26. Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto. Structure Discovery in Bayesian Networks by Sampling Partial Orders. J. Mach. Learn. Res., 17:57:1-57:47, 2016. Google Scholar
  27. Marcin Peczarski. New Results in Minimum-Comparison Sorting. Algorithmica, 40(2):133-145, 2004. Google Scholar
  28. John R. Rice. The algorithm selection problem. Advances in Computers, 15:65-118, 1976. Google Scholar
  29. Herbert J. Ryser. Combinatorial Mathematics, volume 14 of Carus Mathematical Monographs. The Mathematical Association of America, 1963. Google Scholar
  30. Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, and Mikko Koivisto. Counting Linear Extensions in Practice: MCMC versus Exponential Monte Carlo. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, 2018. Google Scholar
  31. Joris van der Hoeven and Grégoire Lecerf. On the bit-complexity of sparse polynomial and series multiplication. J. Symb. Comput., 50:227-254, 2013. Google Scholar
  32. Chris S. Wallace, Kevin B. Korb, and Honghua Dai. Causal Discovery via MML. In Proceedings of the 13th International Conference on Machine Learning, pages 516-524. Morgan Kaufmann, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact