Covering skew-supermodular functions by hypergraphs of minimum total size

✍ Scribed by Attila Bernáth; Tamás Király

• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 1020 KB
• Volume: 37
• Category: Article
• ISSN: 0167-6377
• DOI: 10.1016/j.orl.2009.04.002

✦ Synopsis

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 p 1 and p 2 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 p 1 and p 2 . We also give some applications concerning the connectivity augmentation of hypergraphs.