Minimum sub-tree of a graph that covers each color at least once

Question

I have a connected graph $G$ with $k$ different colors assigned to $n$ nodes where $k<n$. All edges have unit weight.

I want to figure out an algorithm to find a minimum sub-tree of $G$ that covers all $k$ colors (i.e., such that for each color, there is at least one node of this sub-tree with that color; and minimizing the number of nodes in this sub-tree).

I have tried a lot about solving this problem. For $k=2$, the problem will have just one edge, and for $k=3$, it becomes tricky. For $k = n$, the problem becomes as simple as reporting any spanning tree of the graph. For any other $k$, I am not able to think of a definite solution.

Is the problem NP-hard? If so, I will be very grateful if someone can explain or a hint as to which NP-hard problem can be reduced to this problem.

Answer 1

The OP has noticed that "for k=3, it becomes tricky". Indeed, the problem with variable $k$ with respect to $|V|$ is NP-complete and, hence, NP-hard.

Let us formalize the problem so as to able to prove it rigorously. This colored nodes covering problem, called for brevity CNC, is defined in decisional form as follows:

Instance:

• a connected graph $G = (V, E)$;
• a positive integer $k\le|V|$ and a map $C:V\to\{1, 2, \cdots, k\} $, called coloring map with $|C(V)|=k$;
• a positive integer $m$

Question: Is there a subtree $T=(V', E')$ of $G$ that $|E'|\le m$ and $|C(V')|= k$?

Claim: Colored nodes covering problem (CNC) is NP-complete with respect to $|V|$.

---

Proof of the Claim.

It is easy to see that CNC is in NP. Let us reduce the Steiner tree problem, called for brevity ST, one of the NP-complete problems in Karp's original paper to CNC.

Let us recall ST can be defined in decisional form as follows:

Instance:

• a connected graph $G = (V, E)$;
• a subset of the nodes $R\subseteq V$ , called terminal nodes;
• a positive integer $m$.

Question: is there a subtree of $G$ that includes all the nodes of $R$ and that contains at most $m$ edges?

Let us show a polynomial-time reduction from ST to CNC by building an instance of CNC starting from a generic instance of ST. Given a generic instance $s$ of ST, defined by a graph $g=(V,E)$, the set of terminals $R=\{v_1, v_2, \cdots, v_k\}\subseteq V$, and the upper-bound $m$, define an instance $c$ of CNC as the following.

• the same graph $G=(V,E)$.
• the coloring $C: V\to\{1,\,2,\,\cdots,k,\,k+1\}$, $C(v_i)=i$ for $1\le i\le k$ and $C(v)=k+1$ otherwise.
• the same upper bound $m$.

If the induced graph $G[R]$ is connected, then both $s$ and $c$ can be determined in polynomial time in $|V|$ (in fact, constant time), since the spanning tree of $G[R]$ is a tree with the minimal number, $k-1$ of edges that can include all vertices of $R$.

Otherwise let us assume $G[R]$ is not connected. Then any subtree of $G$ that contains all nodes of $R$ must contain at least one node that is not in $R$, which must be colored $k+1$. For any subtree $H$ of $G$, $H$ includes all the nodes of $R$ and contains at most $m$ edges if and only if $H$ includes nodes of every possible color under $C$ and contains at most $m$ edges. That is, $s$ has a yes answer if and only if $c$ has a yes answer.

It is easy to see that the transformation from $s$ to $c$ can be done in polynomial time (in fact, constant time). So we have reduced ST to CNC by a polynomial-time reduction.

---

Bonus exercise: is the colored nodes covering problem with fixed $k$ NP-hard? This is not an easy exercise. Here is a hint.

No. My first step toward demonstrating the existence of a polynomial algorithm is noticing that there will be at most $|V|^k$ choices of the nodes in the subtree that will be mapped to all colors. ($|V|^k$ can be lowered to $(|V|/k + 1)^k$, which does not affect the logic though). It will take some time to reach a full proof.