Covering a crossing supermodular function with pairwise non-parallel arcs

Definitions and mathematical statement

Let $V$ be finite and $p:2^V\to\mathbb Z$ satisfy $p(\varnothing)=p(V)=0$. Call $p$ crossing supermodular if \[ p(X)+p(Y)\le p(X\cap Y)+p(X\cup Y) \] whenever $X\cap Y$, $X\setminus Y$, $Y\setminus X$, and $V\setminus(X\cup Y)$ are all nonempty. For a loopless digraph $D=(V,A)$, let $\rho_D(X)$ count arcs whose tail lies outside $X$ and whose head lies inside $X$.

Determine the minimum size of an arc set satisfying \[ \rho_D(X)\ge p(X)\quad(X\subseteq V),\qquad A\subseteq\{(u,v):u,v\in V,\ u\ne v\}. \] Thus each ordered pair may be used at most once, while the two opposite arcs $(u,v)$ and $(v,u)$ may both occur. Seek an effective feasibility criterion, a characterization of the optimal value, and an attaining construction; assign value $\infty$ when no feasible digraph exists.

The prohibition on parallel arcs is central. Unrestricted multiarc coverings obey different conditions and may meet demands that no simple digraph can meet. For example, a necessary condition here is $p(X)\le |X|\,|V\setminus X|$ for every $X$, but the problem asks for the complete interaction of all cut requirements, not just their individual upper bounds.

Short English statement

How many distinct directed arcs are needed to cover all demands of a crossing-supermodular function when repeated parallel arcs are forbidden?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000022 (AMR-029-0022), 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 pairwise non-parallel arcs. Original source indexed by AMR-029-0022. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Covering a crossing supermodular function with pairwise non-parallel arcs. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Covering_a_crossing_supermodular_function_with_pairwise_non-parallel_arcs.