{"ID":2862298,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.01392","arxiv_id":"2510.01392","title":"The Steiner Path Aggregation Problem","abstract":"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.","short_abstract":"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 goa...","url_abs":"https://arxiv.org/abs/2510.01392","url_pdf":"https://arxiv.org/pdf/2510.01392v1","authors":"[\"Da Qi Chen\",\"Daniel Hathcock\",\"D Ellis Hershkowitz\",\"R. Ravi\"]","published":"2025-10-01T19:23:58Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}