<p>A spider is a tree with at most one vertex of degree greater than 2. This vertex is called the head of the spider.</p>
<p>I am interested in the following problem: We are given an undirected graph <span class="math-container">$G = (V,E)$</span> with a specified vertex <span class="math-container">$h \in V$</span> (the head), and a set of terminals <span class="math-container">$R \subseteq V$</span>. Also, each edge has a non-negative cost <span class="math-container">$c_e$</span>.</p>
<p>The goal is to compute a minimum-cost spider with head <span class="math-container">$h$</span> and leaves <span class="math-container">$R$</span>.</p>
<p>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?</p>

CC BY-SA 4.0
2022-07-12T11:47:19.607Z
Did  you try solving it via min-cost flow? You want internally node-disjoint paths from the terminals to $h$ of minimum cost.
Chandra Chekuri
CC BY-SA 4.0
2022-07-13T22:54:06.143Z
@ChandraChekuri yeah, that seems to work. Thanks!
Karagounis Z
<ds.algorithms><graph-theory><np-hardness><approximation-algorithms><optimization>
Find the minimum cost spider joining a root to some leaves
Karagounis Z
# Find the minimum cost spider joining a root to some leaves

(Asked by: username_0 on 2022-07-11)

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?

**Tags:** ds.algorithms, graph-theory, np-hardness, approximation-algorithms, optimization

> **Comments:**
> **username_1**: Did  you try solving it via min-cost flow? You want internally node-disjoint paths from the terminals to $h$ of minimum cost.  
> **username_0**: @ChandraChekuri yeah, that seems to work. Thanks!  

---

## 0 answers

