Max Horn SAT and the Minimum Cut Problem in Directed Hypergraphs

In this paper we consider the Maximum Horn Satisfiability problem, which is reduced to the problem of finding a minimum cut on a directed hypergraph. For the latter problem, we propose different IP formulations, related to three different definition of hyperpath weight. We investigate the properties of their linear relaxations, showing that they definea hierarchy. The weakest relaxation is shown to be equivalent to the relaxation of a well known IP formulation of Max Horn SAT, and to a a max-flow problem on hypergraphs. The tightest relaxation, which is a disjunctive programming problem, is shown to have integer optimum. The intermediate relaxation consists in a set covering problem with a possible exponential number of constraints. This latter relaxation provide an approximation of the convex hull of the integer solutions which, as proven by the experimental results given, is much tighter than the one known in the literature.