9
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ There is a O(n^2) deterministic algorithm. $\endgroup$
    – Mike G
    Dec 5, 2012 at 8:03
  • $\begingroup$ @MikeG how to do that ? $\endgroup$
    – AJed
    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$ Dec 7, 2012 at 0:12
  • $\begingroup$ @SashoNikolov Can you give a reference? $\endgroup$
    – Raphael
    Dec 7, 2012 at 17:02

1 Answer 1

16
$\begingroup$

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

$\endgroup$
3
  • $\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, 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
    Dec 5, 2012 at 18:28
  • $\begingroup$ Neat, glad it helped! $\endgroup$
    – Jernej
    Dec 5, 2012 at 19:20

Your Answer

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

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