The geodesic classification problem on graphs

Abstract

We define and study a discrete version of the classical classification problem in the Euclidean space. The problem is defined on a graph, where the unclassified vertices have to be classified taking into account the given classification of other vertices. The vertex partition into classes is grounded on the concept of geodesic convexity on graphs, as a replacement for the Euclidean convexity in the multidimensional space. We name such a problem the Geodesic Classification (GC) problem and consider two variants: 2-class single-group and 2-class multi-group. We propose integer programming based approaches for each considered version of the GC problem along with branch-and-cut algorithms to solve them exactly. We also carry out a polyhedral study of the associated polyhedra, which includes some families of facet-defining inequalities and separation algorithms. Facetness conditions for the single-group case are carried over to the multi-group case. We relate our findings with results from the literature concerning Euclidean classification. Finally, we run computational experiments to evaluate the computational efficiency and the classification accuracy of the proposed approaches by comparing them with some classic solution methods for the Euclidean convexity classification problem.