Fourier meets möbius: fast subset convolution

ABSTRACT

We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of ann-element set n, compute their subset convolution f*g, defined for S⊆ N by [ (f * g)(S) = [T ⊆ S] f(T) g(S/T),,]where addition and multiplication is carried out in an arbitrary ring. Via Möbius transform and inversion, our algorithm evaluates the subset convolution in O(n² 2ⁿ) additions and multiplications, substanti y improving upon the straightforward O(3ⁿ) algorithm. Specifically, if the input functions have aninteger range [-M,-M+1,...,M], their subset convolution over the ordinary sum--product ring can be computed in Õ(2ⁿ log M) time; the notation Õ suppresses polylogarithmic factors.Furthermore, using a standard embedding technique we can compute the subset convolution over the max--sum or min--sum semiring in Õ(2ⁿ M) time.

To demonstrate the applicability of fast subset convolution, wepresent the first Õ(2^k n² + n m) algorithm for the Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the Õ(3^kn + 2^k n² + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent Õ(2ⁿ)-time algorithms for covering and partitioning problems (Björklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).

REFERENCES

• 1: M. Aigner, Combinatorial Theory, Springer, Berlin, 1979.
• 2: Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995 [doi>10.1145/210332.210337]
• 3: Andreas Bjorklund , Thore Husfeldt, Inclusion--Exclusion Algorithms for Counting Set Partitions, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.575-582, October 21-24, 2006 [doi>10.1109/FOCS.2006.41]
• 4: G.E. Blelloch, K. Dhamdhere, E. Halperin, R. Ravi, R. Schwartz, S. Sridhar, Fixed parameter tractability of binary near-perfect phylogenetic tree reconstruction, in: M. Bugliesi, B. Preneel, V. Sassone, I. Wegener (Eds.), Automata, Languages and Programming, 33rd International Colloquium (Venice, July 10--14, 2006), Proceedings, Part I, Lecture Notes in Computer Science 4051, Springer, Berlin, 2006, pp. 667--678.
• 5: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 6: S.E. Dreyfus, R.A. Wagner, The Steiner problem in graphs, Networks 1 (1971/72) 195--207.
• 7: B. Fuchs, W. Kern, D. Mlle, S. Richter, P. Rossmanith, X. Wang, Dynamic programming for minimum Steiner trees, Theory Comput. Syst., to appear.
• 8: B. Fuchs, W. Kern, X. Wang, Speeding up the Dreyfus--Wagner algorithm for minimum Steiner trees, Math. Meth. Oper. Res., to appear.
• 9: Martin Fürer, Faster integer multiplication, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250800]
• 10: Zvi Galil , Oded Margalit, All pairs shortest paths for graphs with small integer length edges, Journal of Computer and System Sciences, v.54 n.2, p.243-254, April 1997 [doi>10.1006/jcss.1997.1385]
• 11: Joseph L. Ganley, Computing optimal rectilinear Steiner trees: a survey and experimental evaluation, Discrete Applied Mathematics, v.90 n.1-3, p.161-171, Jan. 15, 1999 [doi>10.1016/S0166-218X(98)00089-4]
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: J. Guo, R. Niedermeier, S. Wernicke, Parametrized complexity of vertex cover variants, in: FDehne, ALópez-Ortiz, J.-RSack (Eds.), Algorithms and Data Structures, 9th International Workshop (Waterloo, Canada, Aug. 15--17, 2005), Lecture Notes in Computer Science 3608, Springer, Berlin, 2005, pp. 36--48.
• 14: Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
• 15: R. Kennes, Computational aspects of the Moebius transform of a graph, IEEE Transactions on Systems, Man, and Cybernetics 22 (1991) 201--223.
• 16: Mikko Koivisto, An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.583-590, October 21-24, 2006 [doi>10.1109/FOCS.2006.11]
• 17: D.K. Maslen, D.N. Rockmore, Generalized FFTs---a survey of some recent results, in: L. Finkelstein, W.M. Kantor (Eds.), Groups and Computation, II, American Mathematical Society, Providence, RI, 1997, pp. 183--237.
• 18: D. Mlle, S. Richter, P. Rossmanith, A faster algorithm for the Steiner tree problem, in: B. Durand, W. Thomas (Eds.), 23rd Symposium on Theoretical Aspects of Computer Science (Marseille, Feb. 23--25, 2006), Lecture Notes in Computer Science 3884, Springer, Berlin, 2006, pp. 561--570.
• 19: T. Polzin, S.V. Daneshmand, On Steiner trees and minimum spanning trees in hypergraphs, Oper. Res. Lett. 31 (2003) 12--20.
• 20: G.-C. Rota, On the foundations of combinatorial theory. I. Theory of Mbius functions. Z. Wahrscheinlichkeitstheorie und verw. Gebiete 2 (1964) 340--368.
• 21: A. Schnhage, V. Strassen, Schnelle Multiplikation groşer Zahlen, Computing 7 (1971) 281--292.
• 22: J. Scott, T. Ideker, R.M. Karp, R. Sharan, Efficient algorithms for detecting signaling pathways in protein interaction networks, J. Comput. Biol. 13 (2006) 133--144.
• 23: Raimund Seidel, On the all-pairs-shortest-path problem in unweighted undirected graphs, Journal of Computer and System Sciences, v.51 n.3, p.400-403, Dec. 1995 [doi>10.1006/jcss.1995.1078]
• 24: Avi Shoshan , Uri Zwick, All Pairs Shortest Paths in Undirected Graphs with Integer Weights, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.605, October 17-18, 1999
• 25: R.P. Stanley, Enumerative Combinatorics, Vol I, Cambridge University Press, Cambridge, 1997.
• 26: David Michael Warme , Jeffrey S. Salowe, Spanning trees in hypergraphs with applications to steiner trees, University of Virginia, Charlottesville, VA, 1998
• 27: F. Yates, The Design and Analysis of Factorial Experiments, Technical Communication No. 35, Commonwealth Bureau of Soil Science, Harpenden, UK, 1937.
• 28: G. Yuval, An algorithm for finding all shortest paths using N^2.81 infinite-precision multiplications, Inform. Process. Lett. 4 (1976) 155--156.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Theory

Keywords:
Möbius transform, Steiner tree, convolution