We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph) whose associated decision problem is a prominent open problem in NP-completeness. We present a num...
详细信息
We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph) whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time, respectively, output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism. More precisely, this is feasible in polynomial time with O(log(2) n/log log n) suitably guessed bits. This result sheds new light on the complexity of this important problem.
Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including Computer Science, Artificial Intelligence, and...
详细信息
Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including Computer Science, Artificial Intelligence, and Game Theory to mention some of them. It is also one of the few problems whose precise tractability status (in terms of polynomial-time solvability) is still unknown, and now open for more than 25 years. In this paper, we briefly survey computational results for this problem, where we focus on the famous paper by Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. algorithms 21 (1996) 618-628], which showed that the problem is solvable in quasi-polynomial time (and thus most likely not co-NP-hard), as well as on follow-up works. We consider computational aspects including limited nondeterminism, probabilistic computation, parallel and learning-based algorithms, and implementations and experimental results from the literature. The paper closes with open issues for further research. (C) 2007 Elsevier B.V. All rights reserved.
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we prove that this is the case in triangle-free graphs. This answers a quest...
详细信息
ISBN:
(纸本)9783959771009
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we prove that this is the case in triangle-free graphs. This answers a question of Kante et al. Additionally, we show that deciding if a set of vertices of a bipartite graph can be completed into a minimal dominating set is a NP-complete problem.
暂无评论