Acyclic orientation with connectivity prescriptions

Definitions and mathematical statement

Let $G=(V,E)$ be a finite loopless undirected graph and let $k\ge1$. An orientation replaces each edge by one of its two possible directed arcs. It is acyclic if it has no directed cycle. Write $\lambda_D(u,v)$ for the maximum number of pairwise arc-disjoint directed $u$--$v$ paths in an orientation $D$.

For two distinct specified vertices $s,t$, determine the complexity of deciding whether there is an acyclic orientation satisfying \[ \lambda_D(s,v)\ge k,\qquad \lambda_D(v,t)\ge k \quad(v\in V\setminus\{s,t\}). \] The source also asks the following separate variant. Given distinct $s,t_1,t_2$, decide whether an acyclic orientation has $\lambda_D(s,t_1)\ge k$ and $\lambda_D(s,t_2)\ge k$.

In each case, seek a polynomial-time recognition and construction method, or a precise complexity classification. The integer $k$ is part of the input. Paths belonging to a single connectivity requirement must be arc-disjoint; path collections for different destinations may overlap. There is no demand for one simultaneous collection disjoint across all requirements. The orientation must satisfy all the requirements at once. Deleting the acyclicity condition, or replacing path connectivity by local degree inequalities without proving equivalence, gives a different decision problem.

Short English statement

Can one efficiently orient a graph without directed cycles while meeting the specified source-to-vertex and vertex-to-terminal connectivity demands?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000002 (AMR-029-0002), 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: Acyclic orientation with connectivity prescriptions. Original source indexed by AMR-029-0002. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Acyclic orientation with connectivity prescriptions. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Acyclic_orientation_with_connectivity_prescriptions.