ECCC-Report TR06-115https://eccc.weizmann.ac.il/report/2006/115Comments and Revisions published for TR06-115en-usFri, 08 Sep 2006 11:44:39 +0300
Paper TR06-115
| Finding a Heaviest Triangle is not Harder than Matrix Multiplication |
Artur Czumaj,
Andrzej Lingas
https://eccc.weizmann.ac.il/report/2006/115We show that for any $\epsilon > 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^{\omega} + n^{2 + \epsilon})$,
where $\omega $ is the exponent of fastest matrix multiplication
algorithm. By the currently best bound on $\omega$, the running time
of our algorithm is $\O(n^{2.376})$. Our algorithm substantially
improves the previous time-bounds for this problem recently
established by Vassilevska et al. (STOC 2006, $\O(n^{2.688})$) and
(ICALP 2006, $\O(n^{2.575})$). 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(m^{1.41})$.
Fri, 08 Sep 2006 11:44:39 +0300https://eccc.weizmann.ac.il/report/2006/115