On orientations maximizing total arc-connectivity

Summary

For a given digraph D and distinct u,ν ⊆ V(D), we denote by λD (u, ν) the local arc-connectivity from u to v. Further, we define the total arc-connectivity tac (D) of D to be ∑{u,ν}⊆v(D) (λd (u, ν) + λD (ν, u)). We show that, given a graph G and an integer k, it is NP-complete to decide whether G has an orientation G satisfying tag(G) ≥ k. This answers a question of Pekec. On the positive side, we show that the corresponding maximization problem admits a 2/3-approximation algorithm.