I am not a computer scientist so please bear with me if this is a naive question.
- Take any graph, pick a set S of vertices (by some criteria or random).
- 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.