ORIENTING GRAPHS TO OPTIMIZE REACHABILITY

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.