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 -hard even on star graphs and hard to approximate to within some constant factor. On the positive side, we provide an Ω(log log n/log 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.

Acknowledgments

M.E. was supported by a research grant from the Dr. Alexander und Rita Besser-Stiftung. R.S. was supported by a research grant from the Israel Science Foundation (grant no. 385/06). U.Z. was supported by BSF grant no. 2006261. We thank Rani Hod for his help with the proof of Lemma 3.4.

Part of this work was presented at the Workshop on Algorithms in Bioinformatics in the years 2008 [Medvedovsky et al. 08] and 2010 [Gamzu et al. 10].

¹To whom correspondence should be addressed.