Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|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
3  
@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
add comment

1 Answer

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|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
3  
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 –  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
add comment

Your Answer

 
discard

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.