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 InfoMany 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.
Finding two vertices with the most/least common neighbors
graph theory;graph algorithms;time complexity