Covering symmetric skew-supermodular functions with hyperedges

Bernáth, Attila and Király, Tamás (2008) Covering symmetric skew-supermodular functions with hyperedges. Technical Reports. ISSN 1587-4451

Preview

Text (Technical Report) egres_08_05_u_164833.930953.pdf Download (505kB) | Preview

Abstract

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 p1 and p2 are skewsupermodular 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.

Actions (login required)

Edit Item