Publications

Authors:

Raffaele, Alice; Rizzi, Romeo

Title:

New theoretical results on the Monotone Boolean Duality and the Monotone Boolean Dualization problems

Year:

2025

Type of item:

Articolo in Rivista

Tipologia ANVUR:

Articolo su rivista

Language:

Inglese

Referee:

Sì

Name of journal:

DISCRETE APPLIED MATHEMATICS

ISSN of journal:

0166-218X

N° Volume:

361

Page numbers:

347-369

Keyword:

Monotone Boolean function; Hypergraph transversal; Clutter and blocker; Full cover; Quasi-polynomial time; Dualization

Short description of contents:

This work presents a new decomposition for the Monotone Boolean Duality problem, which consists of checking whether two monotone Boolean functions f (described by its unique irredundant DNF) and g (described by its unique irredundant CNF) are equivalent. This coNP problem has 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). Best-known algorithms run in quasi-polynomial time; no polynomial-time algorithm has been discovered yet, even if for many special classes these are known. The exact complexity of the general problem is still an open question. Based on both classical results by Berge (1989) and Fredman and Khachiyan (1996), and also on the concept of full covers used by Boros and Makino (2009) and Elbassioni (2008), we propose a new approach to decompose the problem and obtain new theoretical results. Our scheme offers a strong bound which, in the worst case only, has the same time complexity as Fredman and Khachiyan (1996). Anyway, it better highlights the inherent symmetry of the problem, lets us present another polynomial-space algorithm for the Monotone Boolean Dualization problem, and motivates further study on full covers. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

Product ID:

143138

Handle IRIS:

11562/1146736

Last Modified:

December 10, 2024

Bibliographic citation:

Raffaele, Alice; Rizzi, Romeo, New theoretical results on the Monotone Boolean Duality and the Monotone Boolean Dualization problems «DISCRETE APPLIED MATHEMATICS» , vol. 361 , 2025 , pp. 347-369

Consulta la scheda completa presente nel repository istituzionale della Ricerca di Ateneo