Connecting an unconnected forest of subtrees in a graph?

Question

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:

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?

Answer 1

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.