Advanced

Finding a heaviest triangle is no harder than matrix multiplication

Czumaj, Artur and Lingas, Andrzej LU (2006) In Electronic Colloquium on Computational Complexity TR06-115.
Abstract
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(n2376). Our algorithm substantially

improves the previous time-bounds for this problem recently

established by Vassilevska et al. (STOC 2006, \O(n2688)) and

(ICALP 2006, \O(n2575)). Its asymptotic time complexity

matches that of the fastest known algorithm for finding \emph{a}

triangle (not necessarily a maximum-weight one) in a graph.



By... (More)
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(n2376). Our algorithm substantially

improves the previous time-bounds for this problem recently

established by Vassilevska et al. (STOC 2006, \O(n2688)) and

(ICALP 2006, \O(n2575)). Its asymptotic time complexity

matches that of the fastest known algorithm for finding \emph{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 \emph{any} triangle in a graph with m edges, i.e., in time

\O(m141). (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Book/Report
publication status
published
subject
in
Electronic Colloquium on Computational Complexity
volume
TR06-115
pages
13 pages
publisher
[Publisher information missing]
ISSN
1433-8092
project
VR 2005-4085
language
English
LU publication?
yes
id
5fe4baec-a88d-4263-8831-c507166a7f65 (old id 1671014)
alternative location
http://eccc.hpi-web.de/report/2006/115/
date added to LUP
2010-09-15 13:58:00
date last changed
2016-04-16 06:30:37
@techreport{5fe4baec-a88d-4263-8831-c507166a7f65,
  abstract     = {We show that for any 0, a maximum-weight triangle in an<br/><br>
undirected graph with n vertices and real weights assigned to<br/><br>
vertices can be found in time \O(n+n2+),<br/><br>
where is the exponent of fastest matrix multiplication<br/><br>
algorithm. By the currently best bound on , the running time<br/><br>
of our algorithm is \O(n2376). Our algorithm substantially<br/><br>
improves the previous time-bounds for this problem recently<br/><br>
established by Vassilevska et al. (STOC 2006, \O(n2688)) and<br/><br>
(ICALP 2006, \O(n2575)). Its asymptotic time complexity<br/><br>
matches that of the fastest known algorithm for finding \emph{a}<br/><br>
triangle (not necessarily a maximum-weight one) in a graph.<br/><br>
<br/><br>
By applying or extending our algorithm, we can also improve the<br/><br>
upper bounds on finding a maximum-weight triangle in a sparse graph<br/><br>
and on finding a maximum-weight subgraph isomorphic to a fixed graph<br/><br>
established in the papers by Vassilevska et al. For example, we can<br/><br>
find a maximum-weight triangle in a vertex-weighted graph with m<br/><br>
edges in asymptotic time required by the fastest algorithm for<br/><br>
finding \emph{any} triangle in a graph with m edges, i.e., in time<br/><br>
\O(m141).},
  author       = {Czumaj, Artur and Lingas, Andrzej},
  institution  = {[Publisher information missing]},
  issn         = {1433-8092},
  language     = {eng},
  pages        = {13},
  series       = {Electronic Colloquium on Computational Complexity},
  title        = {Finding a heaviest triangle is no harder than matrix multiplication},
  volume       = {TR06-115},
  year         = {2006},
}