# Covering a crossing supermodular function with graph edges

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

## 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

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