For the minimum SCSS problem, the paper gives a practical, nearly linear-time implementation achieving a performance guarantee of 1:75. The heart of the MEG problem is the minimum SCSS (strongly connected spanning subgraph) problem - the MEG problem restricted to strongly connected digraphs. The algorithm achieves a performance guarantee of 1:75 in the time required for transitive closure. The MEG (minimum equivalent graph) problem is the following: "Given a directed graph, find a smallest subset of the edges that maintains all reachability relations between nodes." This problem is NP-hard this paper gives an approximation algorithm achieving a performance guarantee of about 1:64 in polynomial time. On general graphs for any fixed prime p>1.
We provide a 1.78-approximation for TR1 that improves the 2-approximation mentioned in (2) above. , for any integer p>0, can be solved in linear time for directed acyclic graphs using the ideas in Aho et al. In this paper, our contributions are as follows: in 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.937-938, 1999). 1(2):131-137, 1972).Ī 2-approximation algorithm exists for TR1 (Frederickson and JàJà in SIAM J. 4:1396-1400, 1965) and can be solved in linear time for directed acyclic graphs (Aho et al. 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 (Chiu and Liu in Sci. Have been investigated before in different contexts the best previous results are as follows: ) 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Įxperimental observations with a goal to minimize false positive inferences even if risking false negatives. In this paper we consider the p-ary transitive reduction (TR The novelty of our algorithmic methodology based on nontrivial combinatorial optimization techniques makes it appealing to computational biologists as well. Therefore, we expect that our work will appeal to a broad audience of biologists. Our methodology serves as an important first step in formalizing the logical substrate of a signal transduction network, allowing biologists to simultaneously synthesize their knowledge and formalize their hypotheses regarding a signal transduction network.
#TRANSITIVITY NETWORK ANALYSIS DEFINITION SOFTWARE#
Our software NET-SYNTHESIS is freely downloadable from uic. This is a significant and topical problem because there are currently no high-throughput experimental methods for constructing signal transduction networks, and because the understanding of many signaling processes is limited to the knowledge of the signal(s) and of key mediators’ positive or negative effects on the whole process. Here, we present a novel computational method, and related software, to synthesize signal transduction networks from single and double causal evidences. Furthermore, we believe that the combinatorial technique behind the approximation algorithm for the minimization version might be of interest to other graph connectivity problems as well.
For all problems we establish the following: polynomial time minimization of $|A|$ within ratio 1.5, maximization of $|E-A|$ within ratio 2, MAX-SNP hardness even of the length of simple cycles is limited to 5. A solution $A\subseteq E$ is valid if it gives an equivalent path for every original path. In the second extension (called $p$-ary transitive reduction), we have integer edge labeling and we view two paths as equivalent if they have the same beginning, ending and the sum of labels modulo $p$. First, we allow to declare a set $D\subset E$ and require that a valid solution $A$ satisfies $D\subset A$ (it is sometimes called transitive reduction problem). We study the problem of computing a minimum equivalent digraph (also known as the problem of computing a strong transitive reduction) and its maximum objective function variant, with two types of extensions.