Convergent transfer subgraph characterization and computation

In this paper, we present a precise characterization of the existence of a convergent transfer subgraph in an edge colored directed acyclic graph. Based on the characterization, linear time algorithms are proposed to decide the existence of a convergent transfer subgraph and, if one exists, to construct such a subgraph, respectively. The convergent transfer subgraph (CTS) problem arises from the conformance testing of network communication protocols. An abstraction of the basic question to be answered can be stated in graph theoretical terms as follows: Given an edge colored directed acyclic graph G and two vertices s and t, does G have a CTS(s, t)? G has a CTS(s, t) iff G has a subgraph, H, satisfying the following conditions: 1) s, t belong to H, 2) every vertex of H is reachable from s and reaches t, and 3) in H, the set of edges incident from any vertex v must have the same color and consists of all the edges of G, having the same color, that are incident from v. Previously the best known algorithm to solve the CTS problem was the polynomial time algorithm of Li, Ghriga, and Kabore (2000), having time complexity of O(n(n + e)).