# Covering a crossing supermodular function with graph edges

Given a crossing supermodular function [math]p:2^V\to \mathbb{Z}[/math] satisfying [math]p(\emptyset)=p(V)=0[/math], what is the minimum number of edges of an undirected graph *G* covering *p* (that is, with the property that [math]d_G(X)\ge p(X)[/math] holds for every [math]X\subseteq V[/math])?

## Remarks

The problem of covering a symmetric crossing supermodular function with a minimum number of graph edges (which is an abstract version of global edge-connectivity augmentation problems) was solved by Benczúr and Frank ^{[1]}. Another special case is augmenting a mixed graph with graph edges, solved by Bang-Jensen, Frank and Jackson ^{[2]}. A special case of the problem which is open is the following: given directed hypergraph (in which a hyperedge may have several heads and tails, and a node may even be both: more details to be found in ^{[3]}) and a target connectivity *k*, add a minimum number of graph edges to this directed hypergraph to make it *k*-edge-connected.

## References

- ↑ A. Benczúr and A. Frank,
*Covering symmetric supermodular functions by graphs*, DOI Link, author link - ↑ J. Bang-Jensen, A. Frank and B. Jackson,
*Preserving and increasing local edge-connectivity in mixed graphs*, DOI link, author link - ↑ A. Bernáth,
*Egde-connectivity augmentation of graphs and hypergraphs*, PhD thesis, Eötvös Loránd University, 2009.