Finding a heaviest triangle is not harder than matrix multiplication

Summary, in English

We show that for any ε > 0, a maximum-weight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time O(nω + n2+ε), where ω is the exponent of fastest matrix multiplication algorithm. By the currently best bound on ω, the running time of our algorithm is O(n2.376). Our algorithm substantially improves the previous time-bounds for this problem recently established by Vassilevska et al. (STOC 2006, O(n2.688)) and (ICALP 2006, O(n2.575)). Its asymptotic time complexity matches that of the fastest known algorithm for finding a triangle (not necessarily a maximum-weight one) in a graph.



By applying or extending our algorithm, we can also improve the upper bounds on finding a maximum-weight triangle in a sparse graph and on finding a maximum-weight subgraph isomorphic to a fixed graph established in the papers by Vassilevska et al. For example, we can find a maximum-weight triangle in a vertex-weighted graph with m edges in asymptotic time required by the fastest algorithm for finding any triangle in a graph with m edges, i.e., in time O(m1.41).

• Författare: Artur Czumaj; Andrzej Lingas
• Avdelning/ar: Computer Science
• Publiceringsår: 2007
• Språk: Engelska
• Sidor: 986-994
• Publikation/Tidskrift/Serie: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
• Länkar: http://portal.acm.org/citation.cfm?id=1283489
• Dokumenttyp: Konferensbidrag
• Förlag: Society for Industrial and Applied Mathematics
• Ämne: Computer Science
• Conference name: Symposium on Discrete Algorithms, 2007
• Conference date: 2007-01-07 - 2007-01-09
• Conference place: New Orleans, Louisiana, United States
• Status: Published
• Projekt: VR 2005-4085
• ISBN/ISSN/Övrigt: ISBN: 978-0-898716-24-5