On decomposability of multilinear sets (Q1659675)

The authors consider the problem of decomposability of multilinear sets. A multilinear set \(S\) is defined as the set of binary points \(x,y\) of the form \(y_I = \Pi_{i \in I} x_i\), \(I \in F\), where \(F\) is a family of subsets of \(\{ 1. 2, \dots, n\}\) of cardinality at least equal to \(2\). Using an equivalent hypergraph representation for multilinear sets, necessary and sufficient conditions under which the set \(S\) is decomposable into sets \(S_j\), \(j \in J\), based on the structure of pair-wise intersection hypergraphs are proved. A polynomial-time algorithm for the optimal decomposition of a multilinear set into simpler subsets is proposed. Suggestions for further research are brieftly outlined in the concluding part of the paper.