Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, the closeness centrality of a vertex $i$, denoted by $C(i)$, is defined to be the inverse of the mean distance of $i$ to all other vertices of $G$. (Here the distance $d_{ij}=d_{ji}$ between two vertices $i,j$ is simply the number of edges connecting them, orientation being irrelevant.) Formally $C(i) := \frac{N-1}{\sum_{j \neq i}d_{ij}}$. The denominator of $C(i)$ is the sum of all the distances of vertex $i$ to other vertices, and we may call this its peripherality (with respect to the other vertices) in the graph. Clearly, the lower the peripherality of $i$ the higher its closeness centrality $C(i)$, and vice versa.

My question is: if $G$ is a simple, directed graph of $N$ vertices (labelled by $0,1,...,N-1$) with a total of $N-1$ edges between them, such that every two vertices are connected by a path (not necessarily oriented), and that there is one and only such path between them, then, is there an efficient algorithm $\mathcal A$ for finding any vertex $i^\*$ of G with maximum closeness centrality $C(i^*)$, equivalently, minimal peripherality, with average case time complexity and average case space complexity of $\mathcal O(N)$?

For example, let $G$ be the graph of $10$ vertices, labelled by integers $0,1,...,9$, described by the zero-indexed array $T = [9,1,4,9,0,4,8,9,0,1]$, where if $T[i] = t_i \neq i$ then there is a (directed) edge going from vertex $i$ to vertex $t_i$. Then such an algorithm $\mathcal A$ , if it exists, should return vertex $0$ as the vertex of highest closeness centrality in $G$, namely $1.66$, since it has the smallest total distance (of $15$) to all other $9$ vertices, and it will do so with an average case time and space complexity of $\mathcal O$$(10)$.

Sincerely, Sandeep Murthy.