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.
