There are two questions here:
How to assign the fewest number of checkpoints, so that every vertex is within at most T distance from some checkpoint.
How to spread those checkpoints as evenly as possible.
Question 1 turns out to have a linear-time solution:
First, fix some root node arbitrarily. If this is a level, then some start/spawn point makes a natural choice. Next we define...
greatest = 0
// Initialize least > 0. If least drops to/below 0, it tells us
// this node is covered by a checkpoint deeper in its descendant tree.
least = 1
foreach (child of node)
distance = UncoveredDistance(node)
// We'll use NaN as a special value to indictate this branch should be ignored.
// Greatest represents the depth of the deepest node descended from
// this one that is still not covered by any checkpoint.
greatest = max(greatest, distance)
// least represents the most "spillover" coverage from a checkpoint
// placed deeper in the tree. (Represented as negative uncovered distance)
least = min(least, distance)
// If the spillover completely covers the uncovered nodes in our descendant tree,
// then this whole subtree is covered, with additional coverage to pass upward
if(greatest + least <= 0)
greatest = least
// Include depth from node's parent, so we know whether to place a checkpoint
// before the next hop takes us too far away.
// (Treat the root as having a rootwardEdgeLength of 0)
myDepth = greatest + node.rootwardEdgeLength
// If no later checkpoint could cover this whole subtree, add one now.
if(myDepth > T)
myDepth = node.rootwardEdgeLength - T
// This whole subtree is already covered but without surplus,
// so signal parent node to ignore this branch.
if(myDepth > 0 && greatest <= 0 && least <= 0)
// Pass upward any coverage surplus or shortfall we have.
// Finally, kick off the process at the root:
if(UncoveredDistance(rootNode) > 0)
I've shown a recursive version, but this can also be done in one linear scan by first sorting the nodes in topological order (depending on how you generate your graph, they might already be in such an order)
The trick is that this doesn't necessarily solve question 2, of spreading out the checkpoints equally. It puts off adding a checkpoint for as long as it can, which tends to pull all the checkpoints as close to the root as they can go. So some checkpoints may be arbitrarily close together, and intermediate nodes may be within T range of multiple checkpoints, even though the set of checkpoints is still minimal.
If this is a problem, there may be a post-process we can apply, given a minimal checkpoint set, to jiggle those checkpoints around the topology to a more even spacing.