On the Approximability of Reachability-Preserving Network Orientations

Abstract

We introduce a graph-orientation problem arising in the study of biological networks. Given an undirected graph and a list of ordered source–target vertex pairs, the goal is to orient the graph such that a maximum number of pairs admit a directed source-to-target path. We study the complexity and approximability of this problem. We show that the problem is <inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="uinm_a_604554_o_ilm0001.gif"></inline-graphic>-hard even on star graphs and hard to approximate to within some constant factor. On the positive side, we provide an Ω(log&nbsp;log&nbsp;_n_/log&nbsp;_n_) factor approximation algorithm for the problem on _n_-vertex graphs. We further show that for any instance of the problem there exists an orientation of the input graph that satisfies a logarithmic fraction of all pairs and that this bound is tight up to a constant factor. Our techniques also lead to constant-factor approximation algorithms for some restricted variants of the problem.