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 pr
oblem of orienting a connected graph with cut edges in order to maximi
ze the number of ordered vertex pairs (x,y) such that there is a direc
ted path from x to y. After transforming this problem, we prove a key
theorem about the transformed problem that allows us to obtain a quadr
atic algorithm for the original orientation problem. We also consider
how to orient graphs to minimize the number of ordered vertex pairs jo
ined by a directed path. After showing this problem is equivalent to t
he comparability graph completion problem, we show both problems are N
P-hard, and even NP-hard to approximate to within a factor of 1 + epsi
lon, for some epsilon > 0. (C) 1997 Published by Elsevier Science B.V.