# 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?

• Do you mean whether a vertex is type-A or type-B is given in the input? – xskxzr Jun 13 '18 at 17:30

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

• My guess is this is likely still NP-hard, but I didn't see anything on the Wikipedia page discussing this version, and can't immediately see a reduction. – j_random_hacker Jun 13 '18 at 14:54
• It is indeed NP-hard. – Pål GD Jun 14 '18 at 13:29

The problem is NP-hard.

A connected vertex cover is a vertex cover where the subgraph induced by these vertices is connected. Consider the following connected vertex cover problem (CVC):
Input: a graph and an integer $k$.
Output: whether there is a connected vertex cover of size no more than $k$.

CVC is proved to be NP-hard even if the graph is planar and has maximum degree 4 [1]. I'll reduce CVC to the decision version of this problem (say CDC for simplify).

Given an instance of CVC $G=(V,E)$, for each edge $e\in E$, create a vertex $v_e$. Let $V_E=\{v_e\mid e\in E\}$. Create a new bipartite graph $G'$ whose vertex set is $V\uplus V_E$, and there is an edge between $v\in V$ and $v_e\in V_E$ iff $v$ is an endpoint of $e$ in $G$. The instance of CDC is $G'$ where vertices in $V_E$ are type-A vertices and vertices in $V$ are type-B vertices.

Note a connected vertex cover $U\subseteq V$ of $G$ makes the subgraph of $G'$ induced by $U\cup V_E$ connected, and vice versa. Therefore, the instance of CVC has a solution iff the instance of CDC has a solution.

[1] Garey, Michael R., and David S. Johnson. "The rectilinear Steiner tree problem is NP-complete." SIAM Journal on Applied Mathematics 32.4 (1977): 826-834.

• Nice. So it's NP-hard even in the special case where the type-A and type-B vertices form the two parts of a bipartite graph. – j_random_hacker Jun 14 '18 at 11:24

One starting point could be to take a simpler case: $G=(A \cup B,E)$ is a connected bipartite graph. I think this problem may relate to the Connected dominating set problem (CDS) in this case. The idea would be that if we have a method to solve your problem we could construct a solution to CDS in $G$ because the method could be apply for nodes in A or nodes in B.

• Is CDS on connected bipartite graph NP-hard? If the method returns false, does the answer to CDS is also false? Could you please write a formal proof? – xskxzr Jun 13 '18 at 17:25
• For the CDS on connected bipartite, I have no references actually that is why I just said "may relate to". If the method returns false then it means G was not connected in the first place, but since it is then the method can still returns the set of all "b" marked nodes ? For the proof: I think your answer and the answer of D.W. are better than mine, my approach may not be very useful. – fqueyroi Jun 13 '18 at 18:38