Adding Learning Capabilities to the LEX Algorithm for Computing Minimal Transversals

Abstract

Despite being little known and poorly documented, LEX is part of the family of typical testors-finding algorithms that generally has better performance than other much more divulged similar algorithms. The recently published relationship between typical testors and minimal hitting sets, potentially extends the usefulness and applicability of this algorithm to the hypergraphs and data mining fields. Unfortunately, the high time-complexity of both typical testor algorithms and minimal hitting sets algorithms still remains a major obstacle. Therefore, alternatives that can help overcome difficult problems are constantly being researched. In this paper we propose the inclusion of a symbolic learning behavior into the implementation of the LEX algorithm. The incorporated symbolic learning is a general strategy for optimizing the search process, and thus improves the efficiency of minimal transversals and typical testors algorithms. In addition, the performance of the resulting algorithm is assessed  by using carefully designed benchmark test matrices.