3
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ For future reference, when you edit, don't just append "Edit: more stuff" to the end. Instead, edit the question to be what it should have been from the start. We have revision history, so there's no need to indicate which parts of changed. Thank you! $\endgroup$ – D.W. Aug 17 '15 at 16:10
  • 1
    $\begingroup$ What would happen if each $S_i = \{v_i\}$? How would that be different from the "regular" Steiner tree problem? $\endgroup$ – Nicholas Mancuso Aug 17 '15 at 17:15
  • $\begingroup$ It would be exactly the regular Steiner Tree if all groups are singleton, but i'm interested in the case where groups can have more than one terminal, just no terminal can have more than one group. $\endgroup$ – Thomas Bosman Aug 17 '15 at 18:28
  • $\begingroup$ But that is exactly my point. That special case of Group Steiner Tree covers exactly the regular Steiner Tree problem--which would indicate that this is still NP-hard. $\endgroup$ – Nicholas Mancuso Aug 17 '15 at 18:41
  • $\begingroup$ Sorry for the confusion. I understand it remains NP-hard, what I would like to know is if it remains NP-hard to approximate within some constant factor. As far as I understand the general case is NP-hard to approximate to within $\Omega(log^{2-\epsilon}(k))$ for $k$ groups in the general case. $\endgroup$ – Thomas Bosman Aug 17 '15 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.