Algorithm deciding if a radius of a graph is two Given an unweighted, undirected graph, what is the time complexity to decide if its radius is at most 2? Are there any faster algorithms than doing BFS on each node?
Yes. Given the adjacency matrix representation of a graph, computing its second power will allow you to see what nodes are connected by a path of length at most 2. The fastest known matrix multiplication algorithm is $O(n^{2.373})$, which is better than the $O(VE)$ you would get from doing BFS on each node.