The Steiner path aggregation problem

In the Steiner Path Aggregation Problem , our goal is to aggregate paths in a directed network into a single arborescence without significantly disrupting the paths. In particular, we are given a directed multigraph with colored arcs, a root, and k terminals, each of which has a monochromatic path to the root. Our goal is to find an arborescence in which every terminal has a path to the root, and its path does not switch colors too many times. We give an efficient algorithm that finds such a solution with at most 2 log 4 3 ⁡ k color switches. Up to constant factors this is the best possible universal bound, as there are graphs requiring at least log 2 ⁡ k color switches. • The guarantees of the classic heavy path decomposition are extended to general graphs, within a constant factor. • Dipaths from terminals to a root are aggregated into a single arborescence. • With monochromatic dipaths, the arborescence paths switch colors at most log times. • The algorithm iteratively extends paths of active terminals without allowing cycles.