A new decomposition for the Monotone Boolean Duality Problem on Discrete Applied Mathematics

Finally, the second paper extracted from my Ph.D. thesis has been published in Discrete Applied Mathematics and is available online.

Romeo Rizzi and I worked on the Monotone Boolean Duality and the Monotone Boolean Dualization problems, two fundamental problems in enumeration with several applications and relevance in many research areas (e.g., data mining and knowledge discovery, artificial intelligence, matroid theory, computational biology, and, last but not least, mathematical programming). The former consists of checking whether two monotone Boolean functions (described by their unique irredundant DNF and CNF) are equivalent, whereas the latter, given one of the two, asks to compute the other. Best-known algorithms run in quasi-polynomial time (Fredman and Khachiyan, 1996; Elbassioni, 2008; Boros and Makino, 2009).

As a first contribution, we provided a new recursive algorithm to solve the Monotone Boolean Duality problem. This exploits a variable-based decomposition (Fredman and Khachiyan, 1996) and a full-cover decomposition (Boros and Makino, 2009). The approach we define provides a strong bound, which, however, in the worst case only, is the same as the one of Fredman and Khachiyan (1996). Nevertheless, our scheme seems promising from a practical point of view. Also, the problem is described in another light with more commitment to the symmetry between twe two monotone Boolean functions. We hope this might foster simplifications and further comprehension. We also express an analogy with classical implicit enumeration approaches, like those widely used in operations research or constraint programming. Our second theoretical contribution is that we proved how to adapt our new decomposition to solve the Monotone Boolean Dualization problem using polynomial space only.

Our results do not settle the intriguing open question about the exact complexity class of the two problems. Nevertheless, we wish these encourage the study, development, and experimentation of other decompositions and approaches.