# Algorithm to find all 2-hop neighbors lists in a graph

Given a graph $G = (V,E)$, where $|V| = n$. What is a fast algorithm for generating the collection of all 2-hop neighborhood lists of all nodes in $V$.

Naively, you can do that in $O(n^3)$. With power of matrices, you can do that with $O(n^{2.8})$ using Strassen algorithm. You can do better than this using another matrix multiplication algorithm. Any better method ? Any Las Vegas algorithm ?

-
There is a O(n^2) deterministic algorithm. –  Mike G Dec 5 '12 at 8:03
@MikeG how to do that ? –  AJed Dec 5 '12 at 12:37
@MikeG has found a marvelous quadratic time matrix multiplication algorithm which unfortunately is too small to fit within a stackexchange comment –  Sasho Nikolov Dec 7 '12 at 0:12
@SashoNikolov Can you give a reference? –  Raphael Dec 7 '12 at 17:02

The question really depends on what is the precise definition of a 2-hop. If by a 2-hop you mean the set $$hp(v) = \{ u \mid \mbox{there is a path of length 2 between u and v}\},$$ then the current answer is no, you cannot do it faster than $O(n^{\omega})$ where $\omega$ is the usual constant associated with the complexity of performing the matrix product.
Why? For every vertex $v$ check if $v$ is adjacent to vertex in $hp(v).$ If this is the case then you have found a triangle in your graph. Moreover the graph is triangle free if you do not find a vertex $v$ with this property.
The currently best known algorithm for testing if a graph is triangle-free has time complexity $O(n^{\omega}).$
No there is no proven lower bound but recently, a very surprising connection was found. If you can detect triangles faster than $O(n^{\omega})$ then you can compute the matrix product faster than $O(n^{\omega})$. See the paper "Triangle Detection Versus Matrix Multiplication: A study of Truly Subcubic Reducibility" by Williams and Williams. Here kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf –  Jernej Dec 5 '12 at 18:28