Finding, minimizing, and counting weighted subgraphs

ABSTRACT

For a pattern graph H on k nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of H in a given large graph G on n nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include: The number of copies of an H with an independent set of size s can be computed exactly in O*(2^s n^k-s+3) time. A minimum weight copy of such an H (with arbitrary real weights on nodes and edges) can be found in O(4^s+o(s) n^k-s+3) time. (The O* notation omits (k) factors.) These algorithms rely on fast algorithms for computing the permanent of a k x n matrix, over rings and semirings. The number of copies of any H having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in O(n^{ω k/3} + n^2k/3+o(1)) time, where ω < 2.4 is the matrix multiplication exponent and k is divisible by 3. Similar results hold for other values of k. Also, the number of copies having exactly a prescribed weight can be found within this time. These algorithms extend the technique of Czumaj and Lingas (SODA 2007) and give a new (algorithmic) application of multiparty communication complexity. Finding an edge-weighted triangle of weight exactly 0 in general graphs requires Ω(n^2.5-ε) time for all ε > 0, unless the 3SUM problem on N numbers can be solved in O(N^{2 - ε}) time. This suggests that the edge-weighted problem is much harder than its node-weighted version.

REFERENCES

• 1: Noga Alon , Phuong Dao , Iman Hajirasouliha , Fereydoun Hormozdiari , S. Cenk Sahinalp, Biomolecular network motif counting and discovery by color coding, Bioinformatics, v.24 n.13, p.i241-i249, July 2008 [doi>10.1093/bioinformatics/btn163]
• 2: N. Alon and S. Gutner. Balanced families of perfect hash functions and their applications. In Proc. ICALP, pages 435--446, 2007.
• 3: N. Alon and M. Naor. Derandomization, witnesses for boolean matrix multiplication and construction of perfect hash functions. Algorithmica, 16:434--449, 1996.
• 4: 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]
• 5: N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17:209--223, 1997.
• 6: V. Arvind , Venkatesh Raman, Approximation Algorithms for Some Parameterized Counting Problems, Proceedings of the 13th International Symposium on Algorithms and Computation, p.453-464, November 21-23, 2002
• 7: Ilya Baran , Erik D. Demaine , Mihai Pǎtraşcu, Subquadratic Algorithms for 3SUM, Algorithmica, v.50 n.4, p.584-596, March 2008 [doi>10.1007/s00453-007-9036-3]
• 8: Luca Becchetti , Paolo Boldi , Carlos Castillo , Aristides Gionis, Efficient semi-streaming algorithms for local triangle counting in massive graphs, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401898]
• 9: Andreas Björklund , Thore Husfeldt , Petteri Kaski , Mikko Koivisto, Fourier meets möbius: fast subset convolution, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250801]
• 10: A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto. The fast intersection transform with applications to counting paths. CoRR, abs/0809.2489, 2008.
• 11: Ashok K. Chandra , Merrick L. Furst , Richard J. Lipton, Multi-party protocols, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.94-99, December 1983 [doi>10.1145/800061.808737]
• 12: S. S. Chen, S. Cheung, R. Crawford, M. Dilger, J. Frank, J. Hoagl, K. Levitt, C. Wee, R. Yip, and D. Zerkle. GrIDS -- a graph based intrusion detection system for large networks. In Proc. 19th National Information Systems Security Conference, pages 361--371, 1996.
• 13: Norishige Chiba , Takao Nishizeki, Arboricity and subgraph listing algorithms, SIAM Journal on Computing, v.14 n.1, p.210-223, Feb. 1985 [doi>10.1137/0214017]
• 14: 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]
• 15: N. Courtois, A. Klimov, J. Patarin, and A. Shamir. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In Proc. EUROCRYPT, pages 392--407, 2000.
• 16: Artur Czumaj , Andrzej Lingas, Finding a heaviest triangle is not harder than matrix multiplication, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.986-994, January 07-09, 2007, New Orleans, Louisiana
• 17: Martin Dietzfelbinger, Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes, Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, p.569-580, February 22-24, 1996
• 18: Jörg Flum , Martin Grohe, The Parameterized Complexity of Counting Problems, SIAM Journal on Computing, v.33 n.4, p.892-922, 2004 [doi>10.1137/S0097539703427203]
• 19: J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 20: Michael L. Fredman, On the decision tree complexity of the shortest path problems, Proceedings of the 16th Annual Symposium on Foundations of Computer Science, p.98-99, October 13-15, 1975
• 21: Anka Gajentaan , Mark H. Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry: Theory and Applications, v.5 n.3, p.165-185, Oct. 1995 [doi>10.1016/0925-7721(95)00022-2]
• 22: Boaz Gelbord, Graphical Techniques in Intrusion Detection Systems, Proceedings of the The 15th International Conference on Information Networking, p.253, January 31-February 02, 2001
• 23: Yuri Gurevich , Saharon Shelah, Expected computation time for Hamiltonian path problem, SIAM Journal on Computing, v.16 n.3, p.486-502, June 1987 [doi>10.1137/0216034]
• 24: A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Computing, 7(4):413--423, 1978.
• 25: T. Kawabata and J. Tarui. On complexity of computing the permanent of a rectangular matrix. IECIE Trans. on Fundamentals of Electronics, 82(5):741--744, 1999.
• 26: Aviad Kipnis , Adi Shamir, Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.19-30, August 15-19, 1999
• 27: Ton Kloks , Dieter Kratsch , Haiko Müller, Finding and counting small induced subgraphs efficiently, Information Processing Letters, v.74 n.3-4, p.115-121, May 2000 [doi>10.1016/S0020-0190(00)00047-8]
• 28: S. Landau. Polynomials in the nation's service: using algebra to design the advanced encryption standard. American Mathematical Monthly, 111:89--117, 2004.
• 29: R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824--827, 2002.
• 30: H. Minc. Permanents. Cambridge University Press, New York, NY, USA, 1984.
• 31: J. Nesetril and S. Poljak. On the complexity of the subgraph problem. Commentationes Math. Universitatis Carolinae, 26(2):415--419, 1985.
• 32: Jacques Patarin, Cryptoanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'88, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.248-261, August 27-31, 1995
• 33: M. Patrascu. Personal communication.
• 34: F. Romani. Shortest-path problem is not harder than matrix multiplication. Information Processing Letters, 11:134--136, 1980.
• 35: H. Ryser. Combinatorial mathematics. Wiley &#;amp; Math. Assoc. Amer., 1963.
• 36: T. Schank and D. Wagner. Finding, counting and listing all triangles in large graphs, an experimental study. In Experimental and Efficient Algorithms, pages 606--609, 2008.
• 37: V. Sekar, Y. Xie, D. A. Maltz, M. K. Reiter, and H. Zhang. Toward a framework for internet forensic analysis. In Third Workshop on Hot Topics in Networking (HotNets-III), 2004.
• 38: G. Sundaram and S. S. Skiena. Recognizing small subgraphs. Networks, 25:183--191, 1995.
• 39: Charalampos E. Tsourakakis, Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.608-617, December 15-19, 2008 [doi>10.1109/ICDM.2008.72]
• 40: Virginia Vassilevska , Ryan Williams, Finding a maximum weight triangle in n^3-Δ time, with applications, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132550]
• 41: V. Vassilevska, R. Williams, and R. Yuster. Finding the smallest H-subgraph in real weighted graphs and related problems. In Proc. ICALP, volume 4051, pages 262--273, 2006.
• 42: Ryan Williams, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoretical Computer Science, v.348 n.2, p.357-365, 8 December 2005 [doi>10.1016/j.tcs.2005.09.023]
• 43: G. Yuval. An algorithm for finding all shortest paths using N^2.81 infinite-precision multiplications. Inf. Proc. Letters, 4:155--156, 1976.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Path and circuit problems

General Terms:
Algorithms, Theory

Keywords:
3sum, cliques, paths, subgraph isomorphism, weighted graph