I am Parham Khamsepour, a computer scientist and PhD student at University of Ottawa, specializing in artificial intelligence. I have a strong background in algorithms and data structures, and have experience in solving complex problems through my MSc degree at University of Windsor. I have also been working as a web development mentor, guiding and teaching others in the field. I am particularly motivated by the opportunity to tackle challenging problems and make meaningful contributions to both the field, and others through my skills in problem-solving and software development.

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 ∉ S has the same color as its nearest neighbor in S. This problem is NP-complete. A recent result of Dey, Maheshwari, and Nandy (2021) gives a polynomial-time algorithm for the MCS problem on two-colored trees. A block is a maximal connected set of vertices of the same color. We introduce a variant of the MCS problem, namely the minimum consistent spanning subset problem, for which we require the set S to contain a vertex from every block of the graph such that every vertex v ∈/ S has a nearest neighbor in S that is in the same block as v. We observe that this problem is NP-hard on general graphs. We present a polynomial-time algorithm for this problem on trees. Avaialbe Here