Center of a graph

Question

Given an unoriented tree with weightless edges with N vertices and N-1 edges and a number K find K nodes so that every node from a tree is within S distance of at least one of the K nodes. Also, S has to be the smallest possible S, so that if there were S' < S at least one node would be unreachable in S' steps.

I tried solving this problem, however, I feel that my supposed solution is not very fast. My solution: set x=1 find nodes which are x distance from every node let the node which has the most nodes in its distance be one of the K nodes. recompute for every node whilst not counting already covered nodes. do this till I find K number of K nodes. Then if every node is covered we are done else increase x.

Answer 1

This problem is called p-center, and you can find several papers online about it such as this. It is indeed NP for general graphs, but polynomial on trees, both weighted and unweighted.