Finding Triangles or Independent Sets
share
(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 ±ε)-approximation of the number of triangles in G and finds a witness with high probability in O( n^ω(1-δ)) or O ( ( m n^-2δ)^2ω/ω+1) expected time, provided G has a suitable superlinear number of edges and triangles (where ω < 2.376 is the exponent of matrix multiplication, and ε≤ 0.5, δ≤ 0.25 are positive constants). This limits the range of a conjecture of Pǎtraş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 Ω(1/√(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.
READ FULL TEXT
