Unifying the representation of symmetric crossing families and weakly partitive families

The family of non-trivial minimizers of a symmetric submodular function is symmetric crossing, namely it is closed under the complementation of any member and under the intersection of its crossing members. The family of modules of a graph is weakly partitive, namely it is closed under the intersection, union, and difference of its overlapping members. Any symmetric crossing (resp. weakly partitive) family F ⊆ 2 X has an O ( | X | ) space representation [W. Cunningham and J. Edmonds. A combinatorial decomposition theory. Canadian Journal of Mathematics 32:734–765, 1980. Also in W. Cunninghamʹs thesis (1973); E. Dinitz, A. Karzanov, and M. Lomonosov. On the structure of a family of minimal weighted cuts in a graph. In A. Pridman (Ed.), Studies in Discrete Optimization, pages 290–306, 1976. (in Russian)] (resp. [M. Chein, M. Habib, and M.-C. Maurer. Partitive hypergraphs. Discrete Mathematics 37(1):35–50, 1981; R. Möhring and F. Radermacher. Substitution decomposition for discrete structures and connections with combinatorial optimization. Annals of Discrete Mathematics 19:257–356, 1984]). In [B.-M. Bui-Xuan and M. Habib. A representation theorem for union-difference families and application. In Proceedings of LATINʹ08, LNCS 4957, pages 492–503, 2008] we gave a general framework for representing any set family by a tree. This is a natural extension of the above mentioned result on symmetric crossing families. We here show how our framework also captures, in a non-trivial way, the above mentioned result on weakly partitive families. Among the consequences, this is the first result generalizing both the modular decomposition of a graph and the structural behaviour of the minimizers of a symmetric submodular function.