E cient-Subsumption based on GraphAlgorithms ?
The-subsumption problem is crucial to the eeciency of ILP learning systems. We discuss two-subsumption algorithms based on strategies for preselecting suitable matching literals. The class of clauses, for which subsumption becomes polynomial, is a superset of the deter-ministic clauses. We further map the general problem of-subsumption to a certain problem of nding a clique of xed size in a graph, and in return show that a specialization of the pruning strategy of the Car-raghan and Pardalos clique algorithm provides a dramatic reduction of the subsumption search space. We also present empirical results for the mesh design data set.