Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
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
up vote 13 down vote accepted

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

share|cite|improve this answer
Interesting, do you have a reference for the triangle-free recognition problem. Is there a proven lower bound for this problem ? – AJed Dec 5 '12 at 18:15
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 – Jernej Dec 5 '12 at 18:28
Thanks - i wish i can give you another upvote. – AJed Dec 5 '12 at 18:30
Neat, glad it helped! – Jernej Dec 5 '12 at 19:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.