A linear time algorithm for unique Horn satisfiability (Q1313762): Difference between revisions

The Unique-HornSAT problem asks whether there exists a unique solution to a given Horn satisfiability problem. Here, we propose a linear time Unique-HornSAT algorithm. We use directed hypergraphs to represent Horn formulas; our method combines a hypergraph transformation technique with the search of strongly connected components in a sub-graph. In the proposed implementation, we solve a particular disjoint set union problem, for which linear amortized time algorithms are known. A similar result was obtained independently by Berman, Franco and Schlipf, although they fail to obtain a linear complexity.