Date of Award


Publication Type


Degree Name



Computer Science


dynamic programming;minimum consistent subset


Ahmad Biniaz



Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.


Given a vertex-colored edge-weighted graph, the minimum consistent subset (MCS) problem asks for a minimum subset S of vertices such that every vertex v not in S has the same color as its nearest neighbor in S. This problem has applications in clustering and classification algorithms, specially in finding the optimal number of clusters in k-clustering algorithms. This problem is NP-complete. A recent result of Dey, Maheshwari, and Nandy (2021) gives a polynomial-time algorithm for the MCS problem on trees. In thesis we study the MCS problem on different settings, and discuss some of the shortcomings of the MCS problem for trees. We then intro- duce a variant of the MCS problem, namely the minimum consistent spanning subset (MCSS) problem, for which we require the set S to contain a vertex from every block of the graph, where a block is a maximal connected vertices of the same color. We observe that this problem is NP-hard on general graphs. We present an O(n^4)-time algorithm to find the MCSS on multi-colored weighted trees with n vertices. We also improve the running time for simple classes of trees.