Covering symmetric skew-supermodular functions with hyperedges

Attila Bernáth, Tamás Király

Published in:
Operations Research Letters 37:5 (2009), 345-350.


In this paper we give results related to a theorem of Szigeti that concerns the covering of symmetric skew-supermodular set functions with hyperedges of minimum total size. In particular, we show the following generalization using a variation of Schrijver's supermodular colouring theorem: if p_1 and p_2 are skew-supermodular functions whose maximum value is the same, then it is possible to find in polynomial time a hypergraph of minimum total size that covers both of them. Note that without the assumption on the maximum values this problem is NP-hard. The result has applications concerning the local edge-connectivity augmentation problem of hypergraphs and the global edge-connectivity augmentation problem of mixed hypergraphs. We also present some results on the case when the hypergraph must be obtained by merging given hyperedges.

Bibtex entry:

AUTHOR = {Bern{\'a}th, Attila and Kir{\'a}ly, Tam{\'a}s},
TITLE = {Covering symmetric skew-supermodular functions with hyperedges},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2008},
NUMBER = {TR-2008-05}

Last modification: 13.3.2018. Please email your comments to Tamás Király!