Minimum Consistent Subset Problem for Trees

In the minimum consistent subset (MCS) problem, a connected simple undirected graph G = (V, E) is given in which each vertex is colored by one of the possible colors {c(1), c(2), ..., c(k)}; the objective is to compute a minimum size subset C subset of V such that for each vertex v is an element of V, one of its nearest neighbors in C, with respect to the hop-distance, is of the same color as the color of v. The decision version of the MCS problem is NP-complete even for planar graphs. We propose a polynomial-time algorithm for computing a minimum consistent subset of a bi-chromatic tree.