On orientations and shortest paths (Q1123899)

A digraph \(G'\) is called an orientation of a graph G if \(G'\) is obtained from G by assigning directions to its edges. For a given graph G and m pairs of vertices \((s_ i,t_ i)\) \((i=1,2,...,m)\), an orientation \(G'\) of G is called feasible if for every i \((i=1,2,...,m)\) there is an \(s_ i-t_ i\) path in \(G'\). In this case the set of pairs \((s_ i,t_ i)\) are said to be feasible. It is shown that for a given connected graph G and two pairs of vertices \((i,i')\), \((j,j')\) a feasible orientation \(G'\) of G exists if and only if for every partition of the vertex set of G into two disjoint sets \(V_ 1\), \(V_ 2\), such that \(i,j'\in V_ 1\) and \(i',j\in V_ 2\), there exist at least two edges of G that join vertices of \(V_ 1\) with vertices of \(V_ 2\). An orientation \(G'\) of a connected graph G is called ideal with respect to a given set of pairs of vertices if it does not increase the distances between the members of any of the pairs. The authors describe an efficient algorithm that determines whether an ideal orientation with respect to two given pairs of vertices (and any positive edge-lengths) exists, and if so, it provides an ideal orientation with respect to these pairs of vertices. It is also shown that the problem of recognizing whether or not a given connected graph has an ideal orientation with respect to two given pairs of vertices can be solved in polylogarithmic time on a polynomial number of processors, i.e., the problem is in NC. The problem of determining whether or not a given connected graph G has an ideal orientation with respect to an arbitrary set of pairs of vertices in a graph is shown to be NP-complete.