Covering symmetric supermodular functions with graph edges: A short proof of a theorem of Benczur and Frank

In this note we give a short and relatively simple algorithmic proof of a theorem of Benczur and Frank on covering a symmetric crossing supermodular function with a minimum number of graph edges. Our proof method also implies a deficient form of the theorem. (C) 2017 Elsevier B.V. All rights reserved.