Covering a crossing supermodular function with graph edges

Definitions and mathematical statement

Let $V$ be a finite set and $p:2^V\to\mathbb Z$ satisfy $p(\varnothing)=p(V)=0$. Two sets $X,Y$ cross when all four regions $X\cap Y$, $X\setminus Y$, $Y\setminus X$, and $V\setminus(X\cup Y)$ are nonempty. The function is crossing supermodular when \[ p(X)+p(Y)\le p(X\cap Y)+p(X\cup Y) \] for every crossing pair. No symmetry under complementation is assumed.

An undirected loopless multigraph $G$ on $V$ covers $p$ if the number $d_G(X)$ of edges with exactly one endpoint in $X$ satisfies $d_G(X)\ge p(X)$ for every subset $X$. Parallel edges count separately. Determine the minimum \[ \gamma(p)=\min\{|E(G)|:G\text{ covers }p\}, \] and obtain an effective characterization of this optimum and a construction attaining it. The sought result should describe the obstructions and optimal value in terms of the set function, beyond restating the original graph minimization.

Negative values of $p$ impose no additional restriction, but replacing $p$ by a symmetrized function need not preserve crossing supermodularity. Although every undirected cut has the same size as its complement, the input function is allowed to be asymmetric. Requiring a simple graph would impose a different feasibility restriction and is not the multigraph covering problem specified here.

Short English statement

Find the minimum number of undirected edges needed to satisfy every cut demand of an arbitrary crossing-supermodular function.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000021 (AMR-029-0021), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Covering a crossing supermodular function with graph edges. Original source indexed by AMR-029-0021. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Covering a crossing supermodular function with graph edges. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Covering_a_crossing_supermodular_function_with_graph_edges.