Path-driven orientation of mixed graphs

We consider in this paper two graph orientation problems. The input of both problems is (i) a mixed graph GG whose vertex set is VV and edge set (resp. arc set) is EE (resp.  AA) and (ii) a set P⊆V×VP⊆V×V of source–target pairs. The first problem, called S-GO, is a decision problem introduced by Hassin and Megiddo (1989) and defined as follows: is it possible to find an orientation of GG that replaces each edge (u,v)∈E(u,v)∈E by a single arc (either uvuv or vuvu) in such a way that, for each (s,t)∈P(s,t)∈P, there exists a directed path from ss to tt? Our second problem, called MIN-D-GO, is a minimization problem that can be seen as a variant of S-GO, in which we allow some edges (u,v)∈E(u,v)∈E to be doubly oriented. The goal is then to find an orientation of GG that replaces each edge (u,v)∈E(u,v)∈E by uvuv and/or vuvu in such a way that (i) there exists a directed path from ss to tt for each (s,t)∈P(s,t)∈P and (ii) the number of doubly oriented edges is minimized. We investigate the complexity of S-GO and MIN-D-GO by considering some restrictions on the input instances (such as the maximum degree of GG or the cardinality of PP). We provide several polynomial time algorithms, hardness and inapproximability results that together give an extensive picture of tractable and intractable instances for both problems.