Finding a maximum weight triangle in n3-Δ time, with applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding a maximum weight triangle in n^3-Δ time, with applications

Full text

Pdf (191 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-eighth annual ACM symposium on Theory of computing table of contents

Seattle, WA, USA

SESSION: Session 5B table of contents

Pages: 225 - 231

Year of Publication: 2006

ISBN:1-59593-134-1

Authors

Virginia Vassilevska	Carnegie Mellon University, Pittsburgh, PA
Ryan Williams	Carnegie Mellon University, Pittsburgh, PA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 66, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1132516.1132550 What is a DOI?

ABSTRACT

We present the first truly sub-cubic algorithms for finding a maximum node-weighted triangle in directed and undirected graphs with arbitrary real weights. The first is an O(B • n^3+ω/2) = O(B • n^2.688) deterministic algorithm, where n is the number of nodes, ω is the matrix multiplication exponent, and B is the number of bits of precision. The second is a strongly polynomial randomized algorithm that runs in O(n^3+ω/2 log n) expected worst-case time. To achieve this, we show how to efficiently sample a weighted triangle uniformly at random, out of just those triangles whose total weight falls in some prescribed interval (W₁,W₂) for arbitrary weights W₁ and W₂. Previous approaches to the problem resulted in time bounds with either an exponential dependence on B, or a runtime of the form Ω(n³/(log n)^c). The algorithms are easily extended to finding a maximum node-weighted induced subgraph on 3k nodes in Õ(n^(3+ω)k/2) = O(n^{2.688 k}) time.We give applications to a variety of problems, including a stable matching problem between buyers and sellers in computational economics, and discuss the possibility of extending our approach to a truly sub-cubic algorithm for computing all-pairs shortest paths on directed graphs with arbitrary weights.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	T. M. Chan. All-Pairs Shortest Paths with Real Weights in O(n3/log n) Time. In Proc. WADS, Springer-Verlag LNCS 3608, 318--324, 2005.
	3	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]
	4	D. Gale and L. S. Shapley. College admissions and the stability of marriage. Amer. Math. Monthly 69:9--15, 1962.
	5	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 ]
	6	Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
	7	Xiaohan Huang , Victor Y. Pan, Fast rectangular matrix multiplication and applications, Journal of Complexity, v.14 n.2, p.257-299, June 1, 1998 [doi>10.1006/jcom.1998.0476 ]
	8	A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Computing, 7(4): 413--423, 1978.
	9	Leslie Robert Kerr, The effect of algebraic structure on the computational complexity of matrix multiplication, 1970
	10	Jiří Matoušek, Computing dominances inEn (short communication), Information Processing Letters, v.38 n.5, p.277-278, June 14, 1991 [doi>10.1016/0020-0190(91)90071-O ]
	11	Jürgen Plehn , Bernd Voigt, Finding Minimally Weighted Subgraphs, Proceedings of the 16rd International Workshop on Graph-Theoretic Concepts in Computer Science, p.18-29, June 20-22, 1990
	12	Raimund Seidel, On the all-pairs-shortest-path problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.745-749, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129784]
	13	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
	14	V. Vassilevska, R. Williams, and R. Yuster. Finding the smallest H-subgraph in real weighted graphs and related problems. Manuscript, in preparation.
	15	R. Yuster. Private communication.
	16	G. Yuval. An Algorithm for Finding All Shortest Paths Using N2.81 Infinite-Precision Multiplications. Inf. Proc. Letters 4: 155--156, 1976.
	17	All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM (JACM), v.49 n.3, p.289-317, May 2002 [doi>10.1145/567112.567114]

CITED BY 5

	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
	Virginia Vassilevska , Ryan Williams , Raphael Yuster, All-pairs bottleneck paths for general graphs in truly sub-cubic time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Asaf Shapira , Raphael Yuster , Uri Zwick, All-pairs bottleneck paths in vertex weighted graphs, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.978-985, January 07-09, 2007, New Orleans, Louisiana
	Virginia Vassilevska, Nondecreasing paths in a weighted graph or: how to optimally read a train schedule, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.465-472, January 20-22, 2008, San Francisco, California
	Timothy M. Chan, More algorithms for all-pairs shortest paths in weighted graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA