Résumé
The pioneering work of Belohlavek et al. established a compelling connection between Boolean matrix factorization (BMF) and formal concept analysis (FCA), demonstrating that formal concepts serve as optimal factors for decomposing binary matrices. However, identifying the size-optimal decomposition remains an NP-hard problem, posing significant computational challenges. In this paper, we present a novel reformulation of the Boolean rank computation problem using hypergraph theory. Specifically, we show that the Boolean rank of a matrix corresponds to the size of the minimum transversal of the hypergraph constructed from the intervals of its formal concepts. This reformulation provides a theoretical foundation for understanding the structure of optimal factorizations and offers a new perspective on the problem. To validate our approach, we conducted an extensive experimental study to evaluate the characteristics of the solutions computed by our algorithm. The results demonstrated that our method not only achieved optimal factorizations but also exhibited favorable properties in terms of stability and separation.