TY - JOUR

T1 - Approximation algorithms for orienting mixed graphs

AU - Elberfeld, Michael

AU - Segev, Danny

AU - Davidson, Colin R.

AU - Silverbush, Dana

AU - Sharan, Roded

PY - 2013/4/29

Y1 - 2013/4/29

N2 - Graph orientation is a fundamental problem in graph theory that has recently arisen in the study of signaling-regulatory pathways in protein networks. Given a graph and a list of source-target vertex pairs, one wishes to assign directions to the edges so as to maximize the number of pairs that admit a directed source-to-target path. When the input graph is undirected, a sub-logarithmic approximation is known for this problem. However, the approximability of the biologically-relevant variant, in which the input graph has both directed and undirected edges, was left open. Here we give the first approximation algorithms to this problem. Our algorithms provide a sub-linear guarantee in the general case, and logarithmic guarantees for structured instances.

AB - Graph orientation is a fundamental problem in graph theory that has recently arisen in the study of signaling-regulatory pathways in protein networks. Given a graph and a list of source-target vertex pairs, one wishes to assign directions to the edges so as to maximize the number of pairs that admit a directed source-to-target path. When the input graph is undirected, a sub-logarithmic approximation is known for this problem. However, the approximability of the biologically-relevant variant, in which the input graph has both directed and undirected edges, was left open. Here we give the first approximation algorithms to this problem. Our algorithms provide a sub-linear guarantee in the general case, and logarithmic guarantees for structured instances.

UR - http://www.scopus.com/inward/record.url?scp=84876408416&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2012.03.044

DO - 10.1016/j.tcs.2012.03.044

M3 - Journal articles

AN - SCOPUS:84876408416

SN - 0304-3975

VL - 483

SP - 96

EP - 103

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -