  Network design problems aim to compute low-cost structures such as routes,
trees and subgraphs. Often, it is natural and desirable to require that these
structures have small hop length or hop diameter. Unfortunately, optimization
problems with hop constraints are much harder and less well understood than
their hop-unconstrained counterparts. A significant algorithmic barrier in this
setting is the fact that hop-constrained distances in graphs are very far from
being a metric.
  We show that, nonetheless, hop-constrained distances can be approximated by
distributions over "partial tree metrics." We build this result into a powerful
and versatile algorithmic tool which, similarly to classic probabilistic tree
embeddings, reduces hop-constrained problems in general graphs to
hop-unconstrained problems on trees. We then use this tool to give the first
poly-logarithmic bicriteria approximations for the hop-constrained variants of
many classic network design problems. These include Steiner forest, group
Steiner tree, group Steiner forest, buy-at-bulk network design as well as
online and oblivious versions of many of these problems.
