We consider the problem of computing a minimum cardinality consistent subset. The idea is to replace the training set of examples with as small a consistent subset as possible so as to improve the efficiency of the system while not significantly affecting its accuracy.
The problem of finding a minimum size consistent subset of a set of examples is shown to be NP-complete. A special case is described and is shown to be equivalent to an optimal disc cover problem. A polynomial time algorithm for this optimal disc cover problem is then given.