Incomplete splitting-off in digraphs

Definitions and mathematical statement

Let $D=(V\cup\{s\},A)$ be a finite loopless directed multigraph, with a distinguished vertex $s\notin V$ and integer $k\ge1$. Assume that for every ordered pair of distinct vertices $x,y\in V$ there are $k$ pairwise arc-disjoint directed $x$--$y$ paths in $D$. These paths may pass through $s$; no corresponding connectivity requirement is imposed with $s$ as an endpoint.

A split at $s$ selects an incoming arc $u\to s$ and an outgoing arc $s\to v$, removes them, and adds an arc $u\to v$. If $u=v$, the resulting loop may be discarded, since it contributes to no connectivity between distinct vertices. A collection of split pairs is disjoint when no original arc occurs in two pairs.

Determine the maximum number of pairs that can be split simultaneously while preserving $k$-arc-connectivity between every ordered pair in $V$. Seek a min--max or other effective characterization and a construction attaining the maximum.

The trivial upper bound is $\min\{d_D^-(s),d_D^+(s)\}$, but connectivity can obstruct attaining it when the two degrees differ. The problem does not assume that they are equal. A pair feasible on its own may conflict with another feasible pair; the final graph after all chosen splits must satisfy every connectivity requirement simultaneously.

Short English statement

How many incoming-outgoing arc pairs can be split off at one vertex while preserving the required connectivity among all other vertices?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000043 (AMR-029-0043), 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: Incomplete splitting-off in digraphs. Original source indexed by AMR-029-0043. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Incomplete splitting-off in digraphs. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Incomplete_splitting-off_in_digraphs.