# Find the minimum cost spider joining a root to some leaves

A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider.

I am interested in the following problem: We are given an undirected graph $$G = (V,E)$$ with a specified vertex $$h \in V$$ (the head), and a set of terminals $$R \subseteq V$$. Also, each edge has a non-negative cost $$c_e$$.

The goal is to compute a minimum-cost spider with head $$h$$ and leaves $$R$$.

This problem is a special case of degree-bounded Steiner Tree, where each vertex has an upper bound on its allowed degree. But I was wondering if there is a simpler result in this case?

• Did you try solving it via min-cost flow? You want internally node-disjoint paths from the terminals to $h$ of minimum cost. Jul 12, 2022 at 11:47
• @ChandraChekuri yeah, that seems to work. Thanks! Jul 13, 2022 at 22:54