S-T edge-connectivity augmentation

Definitions and mathematical statement

Let $D=(V,A)$ be a finite loopless digraph, let $S,T\subseteq V$ be possibly overlapping terminal sets, and let $k\ge0$ be an integer given in binary. Added parallel arcs are allowed. An augmentation can be encoded by multiplicities $z_{uv}\in\mathbb Z_{\ge0}$ for distinct $u,v\in V$, of total size $\sum_{u\ne v}z_{uv}$.

Require that, after adding these arcs, every ordered pair $s\in S,t\in T$ with $s\ne t$ have $k$ arc-disjoint directed $s$--$t$ paths. Different terminal pairs can use the same arcs. By the directed edge version of Menger's theorem this is equivalent to \[ |\delta_D^+(X)|+ \sum_{\substack{u\in X\\v\notin X}}z_{uv}\ge k \] for every $X\subseteq V$ with $X\cap S\ne\varnothing$ and $T\setminus X\ne\varnothing$.

Develop a strongly polynomial combinatorial algorithm minimizing the augmentation size and outputting an optimal multiplicity vector. Strongly polynomial means that the number of arithmetic operations is bounded by a polynomial in the graph dimensions, independent of the numerical magnitude of $k$, with intermediate numbers of polynomial bit length. Binary multiplicities prevent a large optimum from forcing an excessively long list of individual arcs.

The source already supplies a min--max characterization and an ellipsoid-based approach, so existence of some optimization formulation is not the requested advance. No terminal is required to connect to itself, and there is no restriction forbidding an added arc already present in $D$.

Short English statement

Find a strongly polynomial combinatorial algorithm for minimum arc augmentation giving k directed paths from every source terminal to every distinct target terminal.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000074 (AMR-029-0074), 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: S-T edge-connectivity augmentation. Original source indexed by AMR-029-0074. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, S-T edge-connectivity augmentation. Individual source statement and remarks. https://lemon.cs.elte.hu/egres/open/S-T_edge-connectivity_augmentation.