Recent results on well-balanced orientations

NEW

Problem: Reconstructed statement. For a finite loopless multigraph $G=(V\cup\{s\},E)$, let $\vec G$ be an orientation. Let $\lambda_G(x,y)$ denote undirected local edge-connectivity and $\lambda_{\vec G}(x,y)$ directed local arc-connectivity. An orientation is best-balanced if it is smooth,

and well-balanced,

For arcs $r\to s$ and $s\to t$, $\vec G_{rt}$ is obtained by deleting them and adding $r\to t$, with underlying split graph $G_{rt}$.

The question asks whether, whenever $\vec G$ is best-balanced and $\varrho_{\vec G}(s)=\delta_{\vec G}(s)$, some such directed split remains best-balanced.

Result: The statement is false.

Let

Take edges

oriented as

At $s$, $\varrho(s)=2=\delta(s)$. The imbalances $\varrho-\delta$ are

so the orientation is smooth.

Let $C=\{u,v,w,x,s\}$. The graph $G[C]$ is $K_5$ minus the two disjoint edges $uv$ and $xs$, hence $\lambda_G(a,b)=3$ for all distinct $a,b\in C$. Pairs involving $p$ or $q$ have undirected connectivity $1$, so require only $0$ directed paths. The digraph on $C$ is strongly connected, since

and also $w\to v$, $v\to s$. Thus $\lambda_{\vec G}(a,b)\ge1=\lfloor 3/2\rfloor$ for all distinct $a,b\in C$. Hence $\vec G$ is best-balanced.

The only possible directed splits at $s$ are:

Each fails to be well-balanced:

In each resulting digraph, no arc leaves the listed cut $X$, so the directed local connectivity for the indicated ordered pair is $0$. But in the corresponding underlying split graph the indicated two vertices have undirected local connectivity $2$: the cut $X$ has size $2$, and there are two edge-disjoint paths, respectively

Thus

in every possible split. Therefore no directed split at $s$ produces a best-balanced orientation.

Citation: Original problem: A. Bernáth, S. Iwata, T. Király, Z. Király, Z. Szigeti, “Recent results on well-balanced orientations,” Discrete Optimization 5 (2008), 663–676, Section 6, Question 3/4. The counterexample above is not from that paper.