Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-010 | 1st December 2005 00:00

Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs



In this paper we consider the p-ary transitive reduction (TR<sub>p</sub>) problem where p>0 is an integer; for p=2 this problem arises in inferring a sparsest possible (biological) signal transduction network consistent with a set of experimental observations with a goal to minimize false positive inferences even if risking false negatives. Special cases of TR<sub>p</sub> has been investigated before in different contexts; the best previous results are as follows:
(1) The minimum equivalent digraph problem, that correspond to a special case of TR<SUB>1</SUB> with no critical edges, is known to be MAX-SNP-hard, admits a polynomial time algorithm with an approximation ratio of 1.617+\eps for any constant \eps>0 and can be solved in linear time for directed acyclic graphs.
(2) A 2-approximation algorithm exists for TR<SUB>1</SUB>.
In this paper, our contributions are as follows:
(a) We observe that TR<SUB>p</SUB>, for any integer p>0, can be solved in linear time for directed acyclic graphs.
(b) We provide a 1.78-approximation for TR<SUB>1</SUB> that improves the 2-approximation mentioned in (2) above.
(c) We provide a 2+o(1)-approximation for TR<SUB>p</SUB> on general graphs for any prime p>0.

ISSN 1433-8092 | Imprint