I am not a computer scientist so please bear with me if this is a naive question.

  1. Take any graph, pick a set S of vertices (by some criteria or random).
  2. Find two vertices in set S with the most/least number of common neighbors.

This feels like a "hard" problem to write an efficient algorithm for, because if set S has n vertices, I might need to make n choose 2 or n(n-1)/2 comparisons. I am hoping to do this "efficiently" in terms of time complexity.

Is there a similar problem in computer science that has been studied, which I can look up in textbooks or research papers?

Edit - Additional Info

Many thanks to the two comments. I should add that I am looking for non-matrix multiplication methods because I am working with a large dataset in a sparse graph format like edgelist or compressed sparse row.

  • 5
    $\begingroup$ for a graph with $n$ vertices this is equivalent to the closest pair problem in the hamming metric in $n$ dimensions. the naive algorithm is $O(n|S|^2)$. For $|S| = \Theta(n)$ you can do $O(n^\omega)$ ($\omega$ - the matrix multiplication exponent) with fast matrix multiplication. $\endgroup$ Feb 7, 2013 at 17:25
  • 3
    $\begingroup$ To add more to Sasho's comment: you can also do it in the time that it takes to multiply an $|S|\times n$ by an $n\times |S|$ matrix. You can do this by blocking the columns for instance in time $O(n/|S|\cdot |S|^\omega)=O(n |S|^{\omega-1})$ time. There are also some (theoretically) faster algorithms for rectangular matrix multiplication that you can use to slightly improve this. $\endgroup$
    – virgi
    Feb 7, 2013 at 19:24
  • $\begingroup$ @SashoNikolov - Is there any non-matrix multiplication methods? E.g. Edgelist or Compressed Sparse Row? I need to do this for a large dataset. Will update the question! $\endgroup$
    – Legendre
    Feb 7, 2013 at 21:08
  • 3
    $\begingroup$ @Legendre: Viewing your problem as matrix multiplication is a very natural approach. More concretely, computing the number of common neighbors for every pair of vertices in S at the same time is equivalent to multiplication between a 0/1 matrix of size |S|×|V| and its transpose. Therefore, forbidding matrix multiplication approaches to your question sounds an unnatural restriction to me. Of course, there might be an algorithm which finds the best pair of vertices more efficiently than computing the number of common neighbors for every pair, but I cannot see how to do it. $\endgroup$ Feb 7, 2013 at 22:01
  • 1
    $\begingroup$ well there is sparse matrix multiplication. i am not sure what you can do there aside from the obvious algorithm. @virgi should know more $\endgroup$ Feb 7, 2013 at 23:32


Your Answer

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