Highly element-connected orientation

Definitions and mathematical statement

Let $G=(V,E)$ be a finite loopless undirected graph and let $T\subseteq V$ be its terminal set. Vertices in $V\setminus T$ are Steiner vertices. The elements that may fail are the edges and the Steiner vertices; terminals are not elements.

Paths are element-disjoint when they have no common edge and no common Steiner vertex. They may meet at terminals, including terminals other than their endpoints. The graph is $q$-element-connected on $T$ if every pair of distinct terminals is joined by $q$ such paths. Equivalently, deleting fewer than $q$ elements cannot disconnect any two terminals.

For every integer $k\ge1$, is the following assertion true? \[ G\text{ is }2k\text{-element-connected on }T \ \Longrightarrow\ G\text{ has a }k\text{-element-connected orientation on }T. \] An orientation chooses a direction for each edge. Its required property means that for every ordered pair of distinct terminals $s,t$, there are $k$ directed element-disjoint paths from $s$ to $t$.

The same orientation must work for all ordered terminal pairs. Paths used for different pairs need not be disjoint from each other; disjointness applies within each family of $k$ paths. Choosing a root and satisfying only the paths from that root is a weaker target. Likewise, ordinary edge-connectivity ignores failure of Steiner vertices and cannot simply replace element-connectivity in the hypothesis. Parallel edges can be retained as distinct elements.

Short English statement

Does twice the required terminal element-connectivity guarantee an orientation preserving the required directed connectivity between every pair of terminals?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000042 (AMR-029-0042), 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: Highly element-connected orientation. Original source indexed by AMR-029-0042. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Highly element-connected orientation. Individual source statement and remarks. https://lemon.cs.elte.hu/egres/open/Highly_element-connected_orientation.