1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Which problems have you already tried reducing from? If you haven't tried any yet, I would suggest spending some time on that direction. What NP-hard problems do you already know that might potentially be relevant? This looks like a nice exercise, but to get the most benefit from it you should probably do the exercise yourself; if we solved it for you, you'd get less out of it. $\endgroup$ – D.W. Feb 1 '18 at 16:49
1
$\begingroup$

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.

$\endgroup$

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.