Horn functions and submodular boolean functions

✍ Scribed by Oya Ekin; Peter L. Hammer; Uri N. Peled

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 953 KB
• Volume: 175
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00202-2

✦ Synopsis

After providing a simple characterization of Horn functions (i.e., those Boolean functions that have a Horn DNF), we study in detail the special class of submodular functions. Every prime implicant of such a function involves at most one complemented and at most one uncomplemented variable, and based on this we give a one-to-one correspondence between submodular functions and partial preorders (reflexive and transitive binary relations), and in particular between the nondegenerate acyclic submodular functions and the partially ordered sets. There is a one-to-one correspondence between the roots of a submodular function and the ideals of the associated partial preorder. There is also a one-to-one correspondence between the prime implicants of the dual of the submodular function and the maximal antichains of the associated partial preorder. Based on these results, we give graph-theoretic characterizations for all minimum prime DNF representations of a submodular function. The problem of recognizing submodular timctions in DNF representation is coNP-complete.