Approximation algorithms for orienting mixed graphs

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

doi:10.1016/j.tcs.2012.03.044

Approximation algorithms for orienting mixed graphs

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

^*Corresponding author for this work

Institute of Theoretical Computer Science

8 Citations (Scopus)

Abstract

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.

Original language	English
Journal	Theoretical Computer Science
Volume	483
Pages (from-to)	96-103
Number of pages	8
ISSN	0304-3975
DOIs	https://doi.org/10.1016/j.tcs.2012.03.044
Publication status	Published - 29.04.2013

Funding

M.E. was supported by a research grant from the Dr. Alexander und Rita Besser-Stiftung. C.R.D. would like to thank Gerry Schwartz, Heather Reisman, and the University of Waterloo-Haifa International Experience Program for funding his visit to the University of Haifa, during which part of this work was done. R.S. was supported by a research grant from the Israel Science Foundation (grant no. 241/11).

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

Access to Document

10.1016/j.tcs.2012.03.044

Cite this

@article{874e2df3ea8a42adbf3ac83c1cc428fb,

title = "Approximation algorithms for orienting mixed graphs",

abstract = "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.",

author = "Michael Elberfeld and Danny Segev and Davidson, \{Colin R.\} and Dana Silverbush and Roded Sharan",

year = "2013",

month = apr,

day = "29",

doi = "10.1016/j.tcs.2012.03.044",

language = "English",

volume = "483",

pages = "96--103",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

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 - https://www.scopus.com/pages/publications/84876408416

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 -

Approximation algorithms for orienting mixed graphs

Abstract

Funding

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this