| Abstract (2006) | |||||||||||||
Abstract | |||||||||||||
| In this paper we consider the p-ary transitive reduction (TRp) 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 TRp have 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 TR1 with no critical edges, is known to be MAX-SNP-hard, admits a polynomial time algorithm with an approximation ratio of 1.617+ε for any constant ε> 0 [13] and can be solved in linear time for directed acyclic graphs [1]. (2) A 2-approximation algorithm exists for TR1 [9, 15]. In this paper, our contributions are as follows: • We observe that TRp, for any integer p> 0, can be solved in linear time for directed acyclic graphs using the ideas in [1]. • We provide a 1.78-approximation for TR1 that improves the 2-approximation mentioned in (2) above. • We provide a 2+o(1)-approximation for TRp on general graphs for any fixed prime p> 1. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||