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 ?

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

1 Answer 1


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

  • $\begingroup$ Interesting, do you have a reference for the triangle-free recognition problem. Is there a proven lower bound for this problem ? $\endgroup$
    – AJed
    Commented Dec 5, 2012 at 18:15
  • 3
    $\begingroup$ 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 $\endgroup$
    – Jernej
    Commented Dec 5, 2012 at 18:28
  • $\begingroup$ Neat, glad it helped! $\endgroup$
    – Jernej
    Commented Dec 5, 2012 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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