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 Dec 5 '12 at 8:03
  • $\begingroup$ @MikeG how to do that ? $\endgroup$ – AJed Dec 5 '12 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$ – Sasho Nikolov Dec 7 '12 at 0:12
  • $\begingroup$ @SashoNikolov Can you give a reference? $\endgroup$ – 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}).$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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