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$
2
  • $\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$ Aug 17, 2015 at 19:57
  • $\begingroup$ I've edited the question. What I meant with hardness result was in the sense of constant factor, logarithmic/polylogarithmicly hard to approximate, not just NP-hardness to solve to optimality. Would you suggest another term that would have made the question clearer? $\endgroup$ Aug 17, 2015 at 20:15

1 Answer 1

0
$\begingroup$

As noted in the second paragraph of section 18.2 of these lecture notes, https://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec18.pdf, one can actually assume that the groups are pairwise disjoint wlog for any Group Steiner Tree instance. Suppose $v$ is a vertex in $k \geq 2$ groups, $g_1, \ldots, g_k$. We can create $k$ dummy nodes, $v_1, \ldots, v_k$ attached to $v$ by edges of cost 0. Then set each dummy node $v_i$ to be in group $g_i$ and remove $v$ from all groups.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.