## Date of Award

6-1-2023

## Publication Type

Thesis

## Degree Name

M.Sc.

## Department

Computer Science

## Keywords

dynamic programming;minimum consistent subset

## Supervisor

Ahmad Biniaz

## Rights

info:eu-repo/semantics/openAccess

## Creative Commons License

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

## Abstract

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.

## Recommended Citation

Khamsepour, Parham, "The Minimum Consistent Spanning Subset Problem on Trees" (2023). *Electronic Theses and Dissertations*. 9348.

https://scholar.uwindsor.ca/etd/9348