In this paper, we present a new class of “Incompatibility Graphs”(IG) for Data Mining. They are used in Supervised Learning for Box Clustering problems, where an instance is given by a training set of observations, classified as positive and negative, and the objective is to predict the class of any new observation. The Box Clustering algorithm outputs a set of clusters corresponding to labeled hyper-rectangles (homogeneous boxes). In an IG, the vertices correspond to positive observations (points in \(R^d\) ), and an edge exists between two vertices if they cannot be clustered together, because all boxes, including both of them contain also some negative points. In this paper, we formalize the notion of IG, and explain how a Box Clustering problem can be modeled using incompatibility graphs. We also show that IGs have an intrinsic interest from a theoretical viewpoint, since we can prove relationships with other well-known graph classes, as, for example, comparability graphs. In particular, for IGs in the plane, we prove strong structural properties, and we provide a list of forbidden induced subgraphs. Furthermore, we show that Incompatibility Graphs can be exploited to solve some key-problems related to Box Clustering, such as the “Maximum Box”and the “Minimum Covering by Boxes”. In fact, we show that these two problems can be formulated as a vertex packing and a vertex coloring on an Incompatibility Graph, respectively, and that one can solve in polynomial time the former and, for two important subclasses of instances, also the latter.
