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 G G whose vertex set is V V and edge set (resp.arc set) is E E (resp. A A ) and (ii)a set P?VV P ? V  V of sourcetarget 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 G G that replaces each edge (u,v)?E ( u , v ) ? E by a single arc (either uv u v or vu v u ) in such a way that, for each (s,t)?P ( s , t ) ? P , there exists a directed path from s s to t t ? 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 G G that replaces each edge (u,v)?E ( u , v ) ? E by uv u v and/or vu v u in such a way that (i)there exists a directed path from s s to t t 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 G G or the cardinality of P P ). We provide several polynomial time algorithms, hardness and inapproximability results that together give an extensive picture of tractable and intractable instances for both problems.
mixed graphs graph orientation algorithmic complexity biological networks