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,

$$|\varrho_{\vec G}(v)-\delta_{\vec G}(v)|\le 1\quad\forall v,$$

and well-balanced,

$$\lambda_{\vec G}(x,y)\ge \big\lfloor \lambda_G(x,y)/2\big\rfloor\quad\forall x\ne y .$$

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

$$V\cup\{s\}=\{p,q,u,v,w,x,s\}.$$

Take edges

$$pw,\ sq,\ us,\ vs,\ sw,\ ux,\ uw,\ wx,\ vx,\ vw$$

oriented as

$$p\to w,\quad s\to q,\quad u\to s,\quad v\to s,\quad s\to w,$$ $$x\to u,\quad w\to u,\quad w\to x,\quad x\to v,\quad w\to v.$$

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

$$p:-1,\ q:1,\ u:1,\ v:1,\ w:-1,\ x:-1,\ s:0,$$

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

$$u\to s\to w\to x\to u$$

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:

$$(u\to s,\ s\to q),\quad (u\to s,\ s\to w),\quad (v\to s,\ s\to q),\quad (v\to s,\ s\to w).$$

Each fails to be well-balanced:

$$\begin{array}{c|c|c|c} \text{split} & \text{new arc} & \text{zero-outgoing cut }X & \text{pair}\\ \hline u s,\ s q & u q & \{u,q\} & (u,v)\\ u s,\ s w & u w & \{v,q,s\} & (v,u)\\ v s,\ s q & v q & \{v,q\} & (v,u)\\ v s,\ s w & v w & \{u,q,s\} & (u,v) \end{array}$$

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

$$u w v,\ u x v;\qquad v w u,\ v x u;\qquad v w u,\ v x u;\qquad u w v,\ u x v.$$

Thus

$$0=\lambda_{\vec G_{rt}}(a,b)<1=\big\lfloor \lambda_{G_{rt}}(a,b)/2\big\rfloor$$

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.