Combinatorial algorithms for Boolean and pseudo-Boolean functions
Xiaorong Sun · 1992
This thesis reports on a series of studies concerning on the one hand, classes of structured Boolean functions, and on the other hand, quadratic pseudo-Boolean optimization. The approach is combinatorial and algorithmic. The central topics revolve around the recognition of structured Boolean functions, their generalizations, and roof duality for quadratic pseudo-Boolean functions. In the first part of the thesis, we give linear-time combinatorial algorithms for recognizing various generalizations of Horn related formulae (A Boolean function f in disjunctive normal form (DNF), is called Horn if each term involves at most one negative variable). In the second part, we present a new efficient algorithm to recognize threshold Boolean functions, i.e., functions for which there exists a hyperplane separating their set of true points from their set of false points. We show also a hierarchy of generalizations of regular Boolean functions, which are themselves natural generalizations of threshold functions. For any of these functions, if the set of minimal true points is given, then the set of maximal false points can be found in polynomial time. A new way of representing positive Boolean functions using disjunctive condensed forms (DCFs) is also studied. Several polynomial algorithms whose inputs are DNFs, are generalized to the case when the inputs are DCFs (which are shorter than DNFs). In the third part, we study the (NP-hard) problem of minimizing quadratic pseudo-Boolean functions, i.e., quadratic real valued polynomials whose variables take only the values 0 and 1. We shall describe a new network flow based algorithm for finding lower bounds of the minimum. This approach gives the same lower bounds as others (such as the roof duality of Hammer, Hansen and Simeone), but provides a faster algorithm to compute the lower bound. The max-flow approach can also quickly identify the optimal values of a subset of variables. Computational results are also reported. To provide better lower bounds than roof duality, we present a new approach called iterated roof duality. It is shown that iterated roof duality applied to a class of quadratic pseudo-Boolean functions which are naturally associated to graphs, provides the exact values of the stability number for the special case of odd $K\sb4$-free graphs.