On orientations maximizing total arc-connectivity

Abstract

For a given digraph $D$ and distinct $u,v\in V(D)$, we denote by ${\lambda }_D(u,v)$ the local arc-connectivity from $u$ to $v$. Further, we define the total arc-connectivity $tac(D)$ of $D$ to be ${\sum }_{\{u,v\}\subseteq V(D)}{\lambda }_D(u,v)+{\lambda }_D(v,u)$. We show that, given a graph $G$ and an integer $k$, it is NP-complete to decide whether $G$ has an orientation $\vec{G}$ satisfying $tac(\vec{G})\ge k$. This answers a question of Pekec. On the positive side, we show that the corresponding maximization problem admits a $\frac{2}{3}$-approximation algorithm.