Covering skew-supermodular functions by hypergraphs of minimum total size

The paper presents results related to a theorem of Szigeti on covering symmetric skew-supermodular set functions by hypergraphs. We prove the following generalization using a variation of Schrijver's supermodular colouring theorem: if p1 and p2 are skew-supermodular functions with the same maximum value, then it is possible to find in polynomial time a hypergraph of minimum total size that covers both p1 and p2. We also give some applications concerning the connectivity augmentation of hypergraphs.