Given an undirected and edge‐weighted graph G together with a set of ordered vertex‐pairs, called st‐pairs, we consider two problems of finding an orientation of all edges in G: min‐sum orientation is to minimize the sum of the shortest directed distances between all st‐pairs; and min‐max orientation is to minimize the maximum shortest directed distance among all st‐pairs. Note that these shortest directed paths for st‐pairs are not necessarily edge‐disjoint. In this paper, we first show that both problems are strongly NP‐hard for planar graphs even if all edge‐weights are identical, and that both problems can be solved in polynomial time for cycles. We then consider the problems restricted to cacti, which form a graph class that contains trees and cycles but is a subclass of planar graphs. Then, min‐sum orientation is solvable in polynomial time, whereas min‐max orientation remains NP‐hard even for two st‐pairs. However, based on LP‐relaxation, we present a polynomial‐time 2‐approximation algorithm for min‐max orientation. Finally, we give a fully polynomial‐time approximation scheme (FPTAS) for min‐max orientation on cacti if the number of st‐pairs is a fixed constant.
