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?

  • $\begingroup$ Do you mean whether a vertex is type-A or type-B is given in the input? $\endgroup$ – 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]$).

  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Jun 13 '18 at 14:54
  • 1
    $\begingroup$ It is indeed NP-hard. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – xskxzr Jun 13 '18 at 17:25
  • $\begingroup$ 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. $\endgroup$ – fqueyroi Jun 13 '18 at 18:38

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.