Graph Orientation Problems and their Application to Orienting Protein Networks

In a graph orientation problem, one is given an undirected graph and a set of source-target vertex pairs. The goal is to orient the edges of the graph so that a maximum number of pairs admit a directed source-to-target path. In this talk I will describe different versions of the graph orientation problem, discuss their complexity and approximability, and present efficient integer linear programming formulations for them. I will demonstrate the utility of these formulations in orienting protein-protein interaction networks to reveal their underlying structure.