Document Open Access Logo

Fast Multi-Subset Transform and Weighted Sums over Acyclic Digraphs

Authors Mikko Koivisto, Antti Röyskö

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.29.pdf
  • Filesize: 462 kB
  • 12 pages

Document Identifiers

Author Details

Mikko Koivisto
  • Department of Computer Science, University of Helsinki, Finland
Antti Röyskö
  • Department of Computer Science, University of Helsinki, Finland

Funding

This work was partially supported by the Academy of Finland, Grant 316771.

Acknowledgements

We thank Petteri Kaski for valuable discussions about the topic of the paper.

Cite As Get BibTex

Mikko Koivisto and Antti Röyskö. Fast Multi-Subset Transform and Weighted Sums over Acyclic Digraphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 29:1-29:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.29

Abstract

The zeta and Moebius transforms over the subset lattice of n elements and the so-called subset convolution are examples of unary and binary operations on set functions. While their direct computation requires O(3ⁿ) arithmetic operations, less naive algorithms only use 2ⁿ poly(n) operations, nearly linear in the input size. Here, we investigate a related n-ary operation that takes n set functions as input and maps them to a new set function. This operation, we call multi-subset transform, is the core ingredient in the known inclusion - exclusion recurrence for weighted sums over acyclic digraphs, which extends Robinson’s recurrence for the number of labelled acyclic digraphs. Prior to this work, the best known complexity bound for computing the multi-subset transform was the direct O(3ⁿ). By reducing the task to rectangular matrix multiplication, we improve the complexity to O(2.985ⁿ).

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Bayesian networks
  • Moebius transform
  • Rectangular matrix multiplication
  • Subset convolution
  • Weighted counting of acyclic digraphs
  • Zeta transform

Metrics

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

References

  1. Rasmus Resen Amossen and Rasmus Pagh. Faster join-projects and sparse matrix multiplications. In 12th International Conference on Database Theory, ICDT ’09, pages 121-126. ACM, 2009. Google Scholar
  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: Fast subset convolution. In 39th ACM Symposium on Theory of Computing, pages 67-74. ACM, 2007. Google Scholar
  3. Andreas Björklund, Petteri Kaski, and Łukasz Kowalik. Counting thin subgraphs via packings faster than meet-in-the-middle time. ACM Trans. Algorithms, 13(4):48:1-48:26, 2017. Google Scholar
  4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  5. Paul Erdős and Joel Spencer. Probabilistic Methods in Combinatorics. Akadémiai Kiadó, Budapest, 1974. Google Scholar
  6. Nir Friedman and Daphne Koller. Being Bayesian about network structure. A Bayesian approach to structure discovery in Bayesian networks. Mach. Learn., 50(1-2):95-125, 2003. Google Scholar
  7. François Le Gall and Florent Urrutia. Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 1029-1046. SIAM, 2018. Google Scholar
  8. François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pages 296-303. ACM, 2014. Google Scholar
  9. Daniel M. Gordon, Oren Patashnik, Greg Kuperberg, and Joel H. Spencer. Asymptotically optimal covering designs. Journal of Combinatorial Theory, Series A, 75(2):270-280, 1996. Google Scholar
  10. Frank Harary and Edgar M. Palmer. Graphical Enumeration, pages 191-194. Academic Press, 1973. Section 8.8 "Acyclic Digraphs". Google Scholar
  11. Haim Kaplan, Micha Sharir, and Elad Verbin. Colored intersection searching via sparse rectangular matrix multiplication. In Twenty-Second Annual Symposium on Computational Geometry, SCG ’06, pages 52-60. ACM, 2006. Google Scholar
  12. Robert Kennes. Computational aspects of the Möbius transformation of graphs. IEEE Transactions on Systems, Man and Cybernetics, 22(2):201-223, 1992. Google Scholar
  13. Mikko Koivisto. Sum-Product Algorithms for the Analysis of Genetic Risks. PhD thesis, Department of Computer Science, University of Helsinki, January 2004. Google Scholar
  14. Robert W. Robinson. Counting labeled acyclic digraphs. In New Directions in the Theory of Graphs, pages 239-273. Academic Press, New York, 1973. Google Scholar
  15. Topi Talvitie, Aleksis Vuoksenmaa, and Mikko Koivisto. Exact sampling of directed acyclic graphs from modular distributions. In Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI 2019, pages 345-352, 2019. Google Scholar
  16. Jin Tian and Ru He. Computing posterior probabilities of structural features in Bayesian networks. In 25th Conference on Uncertainty in Artificial Intelligence, pages 538-547. AUAI Press, 2009. Google Scholar
  17. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. Google Scholar
  18. Frank Yates. The Design and Analysis of Factorial Experiments. Imperial Bureau of Soil Science, 1937. Google Scholar
  19. Raphael Yuster and Uri Zwick. Fast sparse matrix multiplication. ACM Trans. Algorithms, 1(1):2-13, 2005. 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