2
$\begingroup$

If I have a weighted graph $G=(V,E)$ and three subgraphs $T_1$, $T_2$ and $T_3$ in $G$ which are trees and all unconnected from each other.

What is the best way to connect these three trees such that the resultant connected tree is of minimal cost?

If it helps, I have already used the floyd-warshall algorithm to calculate the total distance matrix of $G$.

I was thinking of just iterating over all pairs of vertices $(T_1,T_2)$, $(T_1,T_3)$ and $(T_2,T_3)$ in the distance matrix and find two values from two of those groups that sum to the least. But that feels like it would be very inefficient.

essentially iterating over every vertex almost twice to get the distance values, and then iterating over those values twice again to find the smallest sum. Ending up with a complexity of like $\mathcal{O}(V^3)$ or $\mathcal{O}(V^4)$ or something (forgive me, its been a few years since i did any complexity theory)

Is there a simpler, more efficient solution that I am missing?

EDIT:
I have previously worked out a solution (not necessarily very efficient), to the problem if there are only two trees. Using the distance matrix, I iterate over every pair of vertices in $T_1$ and $T_2$, and then use dijkstra's algorithm to find the shortest path that joins the pair of vertices with the lowest value in the distance matrix.

Am I on the right track at least for the instance where there are only 2 trees? This method seems to get a lot trickier and much less efficient when there are more than 2 trees.

CLARIFICATION:
There seems to have been a bit of confusion (in a subsequently deleted comment) about what I am asking, so I will be more explicit.

The subgraphs $T_1$, $T_2$ and $T_3$ are trees in $G$, but are not connected to eachother.

here is an example:

enter image description here

I am trying to work out a good method of connecting all three trees such that it results in the smallest total cost

From the example I have given, it is pretty trivial to connect $T_2$ and $T_3$, just find an MST over the union of their two vertex sets because they share a single edge. However my problem stems from trying to connect $T_1$ to the rest; there are a lot of ways in which I can draw a path from $T_1$ to the other two, but I want to find the shortest one.

The only way I have thought of so far is to iterate over all the vertices in $T_1$ and see which one is closest to the vertices in $T_2$ and $T_3$ and then use dijkstra to find the shortest path. But this becomes pretty inefficient with very large scale graphs.

So I am looking for a more efficient method of doing this.

I hope that is more clear.

UPDATE:
In response to @D.W.'s answer to my related question here on solving a simplified version of this problem with only two vertex sets.

In order to extend that solution to this, more complicated, instance of the problem with three distinct vertex sets. Do I just need to create 3 dummy vertices $\{t_1,t_2,t_3\}$in $G$ with edge lengths 0 that link to $T_1$, $T_2$ and $T_3$ respectively, and then run dijkstra 3 times: $t_1 \rightarrow t_2$, $t_1 \rightarrow t_3$ and $t_2 \rightarrow t_3$, to find the minimum path $p_1$ that joins two of the three vertex sets; then if, say, the shortest path lay between $t_2$ and $t_3$ then run dijkstra again to find the shortest path $t_1 \rightarrow t_4$ where $t_4$ is a dummy vertex with 0 edge cost linking to the set $\{T_2 \cup T_3 \cup p_1\}$?

Or is that making things too complicated?

$\endgroup$
  • $\begingroup$ Take a look at standard algorithms for computing minimal spanning trees, and consider how you could apply those ideas to your problem. Then you might want to edit your question to show what approaches you've come up with based on that, or even answer your own question if that helps you discover a solution. Another hint: how efficiently can you find the shortest path that goes from some vertex in $T_1$ to some vertex in $T_2$? $\endgroup$ – D.W. Jan 15 '16 at 3:47
  • $\begingroup$ see my update/clarifications. please let me know if you need any more information $\endgroup$ – guskenny83 Jan 15 '16 at 5:41
  • $\begingroup$ @D.W. the best way i can think of to find the shortest path between some vertex $T_1$ to some vertex in $T_2$ is to use dijkstra's algorithm if both vertices are known, and if they are not known and you want the shortest path between the closest vertices, then to construct a distance matrix and iterate over all vertices in $T_2$ for every vertex in $T_1$, find the closest vertex pair and then use dijkstra to find the path between the two, that is how i solved the case for two trees. Are you saying there is a better way of doing that? $\endgroup$ – guskenny83 Jan 18 '16 at 4:01
  • $\begingroup$ Yup, there's a better way of doing that. Start with a simpler case, as a warmup: suppose we have a fixed vertex $v$, and we want to find the shortest path from $v$ to any vertex in $T_2$ (i.e., out of all paths from $v$ to any vertex $w$ such that $w$ is in $T_2$, find the shortest such path). Can you think of how to do that? Think about it for a while, and if you can't see how to do it, ask a new question about how to find the shortest path from some vertex in the set $S$ to some vertex in the set $S'$. $\endgroup$ – D.W. Jan 18 '16 at 4:38
  • $\begingroup$ Thanks so much for all your help, please see my updated question.. $\endgroup$ – guskenny83 Jan 18 '16 at 12:52
2
$\begingroup$

Your problem is known as the group Steiner tree problem, and it is NP-hard. More specifically, in this problem we are given a weighted graph $G=(V,E)$, and $k$ (vertex-disjoint) sets $S_1,S_2,\ldots,S_k \subseteq V$, and asked to find the minimum cost tree that uses at least one vertex from each $S_i$, where $i \in [k]$.

But don't fall into despair yet. Luckily for you, you have a very small number of "terminal trees", specifically three. The good news is that the problem is solvable in polynomial-time for fixed $k$. Moreover, it can be solved in something called FPT time, in fact there is an algorithm solving it running in $2^k n^{O(1)}$ time. When $k = 3$ is fixed, this is polynomial time. Let me shortly describe the idea, or at least give the pointers for a possible algorithm.

Misra et al. [1] observe that group Steiner tree reduces to the so-called directed Steiner out-tree problem. This, in turn, is solvable in a certain time bound using the idea of branching walks (of Nederlof) and inclusion-exclusion. The added nice thing is that the algorithm (as usual with such an inclusion-exclusion approach) needs only polynomial space. Moreover, there is evidence such algorithms are practical too. The Misra et al. [1] paper gives the necessary references.


[1] Misra, N., Philip, G., Raman, V., Saurabh, S., & Sikdar, S. (2012). FPT algorithms for connected feedback vertex set. Journal of combinatorial optimization, 24(2), 131-146.

$\endgroup$
  • $\begingroup$ Nice answer! For the case $k=3$ (i.e., this question) I believe there's a fairly straightforward $O(|E| \log |V|)$-time algorithm for this particular problem, assuming all edge weights are non-negative. See my comment under the question for hints. However, I'm reluctant to just dump the answer to what looks like a nice exercise. $\endgroup$ – D.W. Jan 15 '16 at 7:56
  • $\begingroup$ Thanks for the answer and the link to the paper. Interestingly, what i am trying to do is develop a hybrid approximation algorithm for the steiner tree in graphs with part of it kind of based on the 2-opt algorithm for the TSP. By removing two paths in the full tree I am left with 3 unconnected trees and I want to find an efficient way to connect them again. @D.W. I read your hints, but i am still a bit stuck, is there any more information you could give me? $\endgroup$ – guskenny83 Jan 18 '16 at 3:58

Your Answer

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

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