Does anyone know any constant factor approximation hardness results on Group Steiner Tree when the groups partition the terminals, i.e. every terminal belongs to exactly one group?
The (intuitive) reduction from Set-Cover seems to fail in that case, and it also feels easier. It seems to me you could solve this if the underlying graph is a tree in polynomial time. Is this case still NP-hard to approximate within a constant factor for general graphs?
I've searched for partition/non overlapping/disjoint Group Steiner Tree etc. But I can't find anything, so I imagine this particular variant might have a specific name.
Group Steiner Tree is the following problem:
Instance: a weighted graph $G=(V,E)$, a collection of vertex sets (groups) $S_1,...,S_n \subseteq V$.
Find: a minimum-cost connected subgraph of $G$ that contains at least one vertex of every group $S_i$.
What I am interested in is the special case where there is some set $W \subseteq V$ such that $S_1 \bigcup \cdots \bigcup S_n = W$ and $S_i \bigcap S_j = \emptyset$ for all $i\neq j$.