Minimal number of nodes needed to connect a disconnected graph

Given a graph $G = (V, E)$ with $V = U \uplus T$ (let's say the vertices are
labelled $U$ or $T$), I am looking for the smallest set $U' \subseteq U$ such
that $G[U' \cup T]$ is connected.

If we eleminate all the type-U nodes from the graph, the type-T nodes (terminals) might form several disconnected subgraphs.
That is, the graph $G[T]$ on only the "terminal nodes" might be disconnected,
and I want to pick as few vertices from $U$ as possible to make the graph
connected again.

What kind of graph problem does this relate to?

I think you are looking for the vertex version of the Steiner tree where

• $A$ is the set of terminal nodes and

• $B$ is the set of vertices you want to use to create a tree.

In the Vertex-Weighted Steiner Tree problem you are given a graph $G = (V,E)$ and a set of terminal nodes $T \subseteq V$ and are asked for a minimum set $U$ such that $T \subseteq U$ and $G[U]$ is connected.

This problem has been studied as the node‐weighted Steiner tree problem by

• Segev, 1987, The node‐weighted steiner tree problem, Networks.

• Yeh and Chang, 1998, Weighted connected domination and Steiner trees in distance-hereditary graphs, Discrete Applied Mathematics.

and is indeed NP-complete.

On the positive side, it might be solvable in time $3^k \text{poly}(n)$ where $k$ is the number of connected components in $G[T]$. The simplest preprocessing step is to contract all the edges in $G[T]$ first, that is, replace all the connected components with a single node, and remove parallel edges. (That is, it is fixed-parameter tractable (FPT) in the number of connected components in $G[T]$).

StackExchange Computer Science Q#93047, answer score: 2