Wang and Shroff (2010) proposed a graph-theoretic characterization of pairwise intersession network coding based on paths with controlled edge-overlap. They showed that the solvability of networks with two unit-rate multicast sessions can be decided in polynomial time. Wang and Shroff’s characterization generalizes the edge-disjoint path characterization of noncoded network communication, which is a very important property of their characterization. Then, Song et al. (2013) presented a characterization to the problem based region decomposition method, which determines the solvability in O(|E|) time, where |E| is the number of links. This paper presents a new version of Wang and Shroff’s characterization based region decomposition. We prove that this version of their characterization decides the solvability in O(|E|) time. This version of the characterization concludes a very easy algorithm to diagnose the solvability such that it is only based on the parents of sink regions, which yields a fast method to diagnose solvability or non-solvability of networks with two unit-rate multicast sessions
