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:
@techreport{egres-08-05,
AUTHOR | = | {Bern{\'a}th, Attila and Kir{\'a}ly, Tam{\'a}s}, |
TITLE | = | {Covering symmetric skew-supermodular functions with hyperedges}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2008}, |
NUMBER | = | {TR-2008-05} |