# 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. Dec 5, 2012 at 8:03
• @MikeG how to do that ?
– AJed
Dec 5, 2012 at 12:37
• @MikeG has found a marvelous quadratic time matrix multiplication algorithm which unfortunately is too small to fit within a stackexchange comment Dec 7, 2012 at 0:12
• @SashoNikolov Can you give a reference?
– Raphael
Dec 7, 2012 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 Dec 5, 2012 at 18:28