If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf.
I am sure this problem has been studied before. Does anybody know the name of this problem or an algorithm for solving it?
To find a vertex of maximum distance from any leaf, you can perform a breadth-first search starting from many starting points, i.e. the leaves. Because a BFS visits each node by the shortest possible path from the source(s) of the search, we can easily attribute to each node the distance to the nearest leaf.
Insert into a queue a collection of pairs $(\ell,0)$ for $\ell$ ranging over all leaves, and record $\textrm{max} = 0$.
Repeat the following until the queue is empty:
Pop a pair $(v,d)$ off the queue. If $d = \textrm{max}$, insert $v$ in a collection of maximum-distance elements.
If there are nodes adjacent to $v$ which haven't been visited, push a pair $(w,d+1)$ into the queue for each such neighbour $w$, marking them as having been visited. If there are any such $w$ at all, empty the collection of maximum-distance elements (if it is non-empty), and set $\textrm{max} = d+1$.
The result is a collection of nodes which are all at distance at least $\textrm{max}$ from any leaf.
Let $n = |V|$ (note that $m = |E| = n-1$). Assuming that we can populate the queue with the leaves of the tree in time $O(n)$ by examining all nodes of the graph, and that the vertices have adjacency lists of their neighbours, we "traverse" each edge twice to consider the neighbours of each vertex; then this algorithm takes $O(n+m) = O(n)$ time. It also works for non-trees, taking again $O(n+m)$ time.
Perform breadth-first seach from all leaves in parallel, i.e. visit all neigbours of all leaves, then their respective neighbours, and so on. The node visited last is your winner.
If you let all searches share the visited flag, no vertex is visited twice. Since we have a tree, also every edge is visited only once. In total, we get linear runtime (in the number of nodes).
