(I) We revisit the algorithmic problem of finding all triangles in a graph $G=(V,E)$ with $n$ vertices and $m$ edges. According to a result of Chiba and Nishizeki (1985), this task can be achieved by a combinatorial algorithm running in $O(m^{3/2})$ time. We derive this worst-case bound from first principles and with a simple proof. We then provide a combinatorial algorithm for finding all triangles in a graph and show that is amenable to the same running time analysis. We also show that the running time of such an algorithm cannot be improved in the worst-case and for the entire range of parameters $m$ and $n$. Our arguments are extended to the problem of finding all small complete subgraphs of a given fixed size. (II) Given a graph $G=(V,E)$ with $n$ vertices and $m$ edges, we present a randomized algorithm that computes a $(1 \pm \varepsilon)$-approximation of the number of triangles in $G$ and finds a witness with high probability in $O\left( n^{\omega(1-\delta)} \right)$ or $O \left( \left( m n^{-2\delta} \right)^{\frac{2\omega}{\omega+1}} \right)$ expected time, provided $G$ has a suitable superlinear number of edges and triangles (where $\omega < 2.376$ is the exponent of matrix multiplication, and $\varepsilon \leq 0.5$, $\delta \leq 0.25$ are positive constants). This limits the range of a conjecture of P\v{a}tra\c{s}cu (2010) regarding the triangle detection problem. (III) We present an algorithm which given a graph $G=(V,E)$ performs one of the following tasks in $O(m+n)$ (i.e., linear) time: (i) compute a $\Omega(1/\sqrt{n})$-approximation of a maximum independent set in $G$ (a well-known NP-hard problem), or (ii) find a triangle in $G$. The run-time is faster than that for any previous method for each of these tasks. A series of trade-off results is also available.
翻译:(I) 我们重新审视在 $G = (V,E) 图形中找到所有三角形的算法问题。 根据 Chiba 和 Nishizeki (1985) 的结果, 可以通过以$(m%3/2}) 时间运行的组合算法来完成这项任务。 我们从最初的原则中得出这个最坏的情况, 并且有一个简单的证明。 我们然后提供一个组合算法, 在一个图形中找到所有三角形, 并且显示可以进行相同的时间分析。 我们还表明, 在最坏的情形下, 以及整个参数范围, 美元 美元 美元 和美元 美元 。 我们的论点可以扩大到找到所有以美元( V, E) 以美元和 美元为单位的正数 。