Approximation Algorithms for Orienting Mixed Graphs

Michael Elberfeld, Danny Segev, Colin R. Davidson, Dana Silverbush, Roded Sharan


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 ordered source-target vertex pairs, it calls for assigning directions to the edges of the graph 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 the 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 algorithm to this problem. Our algorithm provides a sub-linear guarantee in the general case, and logarithmic guarantees for structured instances.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching
EditorsRaffaele Giancarlo, Giovanni Manzini
Number of pages13
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Publication date06.2011
ISBN (Print)978-3-642-21457-8
ISBN (Electronic)978-3-642-21458-5
Publication statusPublished - 06.2011
Event22nd Annual Symposium, CPM 2011 - Palermo, Italy
Duration: 27.06.201129.06.2011


Dive into the research topics of 'Approximation Algorithms for Orienting Mixed Graphs'. Together they form a unique fingerprint.

Cite this