UC Riverside

It is well known that every 2-edge-connected graph can be oriented so that the resulting digraph is strongly connected. Here we study the problem of orienting a connected graph with cut edges in order to maximize the number of ordered vertex pairs (x, y) such that there is a directed path from x to y. After transforming this problem, we prove a key theorem about the transformed problem that allows us to obtain a quadratic algorithm for the original orientation problem. We also consider how to orient graphs to minimize the number of ordered vertex pairs joined by a directed path. After showing this problem is equivalent to the comparability graph completion problem, we show both problems are NP-hard, and even NP-hard to approximate to within a factor of 1 + ε, for some ε > 0. © 1997 Published by Elsevier Science B.V.