Complexity of some graph-based bounds on the probability of a union of events

Starting from the work of Bonferroni more than one century ago, several methods have been proposed in the literature for the problem of finding upper bounds for the probability of the union of n events when the individual probabilities of the events as well as the probabilities of all intersections of k-tuples of these events are known. The most popular methods for obtaining bounds are based either on a linear programming formulation of the problem or on graph techniques. Some of the graph-based bounds are based on a greedy algorithm and can be found in polynomial time. For most other graph-based bounds proposed in the literature, only heuristic algorithms have been provided to find the best bound with no attempt to solve the problem exactly or to determine its computational complexity. Here we show that the problems of finding the best graph bounds based on cherry trees or on chordal graphs are both NP-complete. Furthermore, we propose a heuristic method to efficiently find a good upper bound based on the chordal graph approach.