TR-2008-05

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:

@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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2008},
NUMBER	=	{TR-2008-05}

}