Minimum Consistent Set Problem

Anil Maheshwari 

Professor

Carleton University

ABSTRACT

Let G=(V,E) be a simple undirected graph, where each vertex is assigned a color from the set {1,2,...,c}. A subset V' of V is said to be a consistent set if, for every vertex v in V, at least one of its nearest neighbors in V' shares the same color as v. We will outline some computational complexity results for finding a minimum size consistent set in geometric and graph theoretic setting.