Monotone Dualization and Generating Hypergraph Transversals

Title: Monotone Dualization and Generating Hypergraph Transversals

Abstract: This research focuses on the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), which is a significant open problem in NP-completeness. The study presents new polynomial time and output-polynomial time results for significant cases, advancing the tractability frontier and improving on previous results. Furthermore, the paper shows that duality of two monotone CNFs can be disproved with limited nondeterminism, which sheds new light on the complexity of this important problem.

Research Question: Can we find efficient algorithms for monotone dualization and generating hypergraph transversals?

Methodology: The research uses the prime CNF of a monotone Boolean function and the concept of duality to study the problem of dualizing a monotone CNF. The study considers the problem of computing all minimal transversals of a hypergraph, which is equivalent to the problem of dualizing a monotone CNF. The paper proposes new algorithms and techniques to solve these problems efficiently.

Results: The research presents new polynomial time and output-polynomial time results for significant cases, which advance the tractability frontier and improve on previous results. The study also shows that duality of two monotone CNFs can be disproved with limited nondeterminism, which sheds new light on the complexity of this important problem.

Implications: The results of this research have significant implications for various application areas such as database theory, machine learning and data mining, artificial intelligence, mathematical programming, and distributed systems. The study advances our understanding of the complexity of monotone dualization and generating hypergraph transversals, which are fundamental problems in computer science.

Link to Article: https://arxiv.org/abs/0204009v2 Authors: arXiv ID: 0204009v2