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

摘要

(Chiu and Liu in Sci. Sin. 4:1396-1400, 1965) and can be solved in linear time for directed acyclic graphs (Aho et al. in SIAM J. Comput. 1(2): 131-137, 1972). (2) A 2-approximation algorithm exists for TR_1 (Frederickson and JaJa in SIAM J. Comput. 10(2):270-283, 1981; Khuller et al. in 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 937-938, 1999). In this paper, our contributions are as follows: 1. We observe that TR_p, for any integer p > 0, can be solved in linear time for directed acyclic graphs using the ideas in Aho et al. (SIAM J. Comput. 1(2): 131-137, 1972). 2. We provide a 1.78-approximation for TR_1 that improves the 2-approximation mentioned in (2) above. 3. We provide a 2 + o(1)-approximation for TR_p on general graphs for any fixed prime p > 1.