TR06-115 Authors: Artur Czumaj, Andrzej Lingas

Publication: 8th September 2006 11:44

Downloads: 1339

Keywords:

We 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})$.