Name
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 NP-hard even on star graphs and hard to approximate to within some constant factor. On the positive side, we provide an O(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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1080/15427951.2011.604554 | INTERNET MATHEMATICS |
Keywords | Field | DocType |
biological network,satisfiability,star graph | Block graph,Discrete mathematics,Combinatorics,Comparability graph,Graph property,Vertex cover,Pathwidth,Longest path problem,Feedback arc set,Mathematics,Feedback vertex set | Journal |
Volume | Issue | ISSN |
7 | 4 | 1542-7951 |
Citations | PageRank | References |
4 | 0.49 | 11 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Elberfeld | 1 | 115 | 10.63 |
| Vineet Bafna | 2 | 1967 | 226.80 |
| Iftah Gamzu | 3 | 146 | 16.34 |
| Alexander Medvedovsky | 4 | 25 | 1.63 |
| Danny Segev | 5 | 233 | 17.05 |
| Dana Silverbush | 6 | 11 | 2.42 |
| Uri Zwick | 7 | 3586 | 257.02 |
| Roded Sharan | 8 | 2792 | 186.61 |