Finding a heaviest triangle is no harder than matrix multiplication
Author
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(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).
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).
Department/s
- Computer Science
Publishing year
2006
Language
English
Publication/Series
Electronic Colloquium on Computational Complexity
Document type
Report
Publisher
[Publisher information missing]
Topic
- Computer Science
Status
Published
Project
- VR 2005-4085
Report number
TR06-115
ISBN/ISSN/Other
- ISSN: 1433-8092