Reachability

In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s ) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with s and ends with t . In an undirected graph, reachability between all pairs of vertices can be determined by identifying the connected components of the graph. Any pair of vertices in such a graph can reach each other if and only if they belong to the same connected component; therefore, in such a graph, reachability is symmetric ( s reaches t iff t reaches s ). The connected components of an undirected graph can be identified in linear time. The remainder of this article focuses on the more difficult problem of determining pairwise reachability in a directed graph (which, incidentally, need not be symmetric).

In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s ) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with s and ends with t . In an undirected graph, reachability between all pairs of vertices can be determined by identifying the connected components of the graph. Any pair of vertices in such a graph can reach each other if and only if they belong to the same connected component; therefore, in such a graph, reachability is symmetric ( s reaches t iff t reaches s ). The connected components of an undirected graph can be identified in linear time. The remainder of this article focuses on the more difficult problem of determining pairwise reachability in a directed graph (which, incidentally, need not be symmetric). For a directed graph G = (V, E) , with vertex set V and edge set E , the reachability relation of G is the transitive closure of E , which is to say the set of all ordered pairs (s,t) of vertices in V for which there exists a sequence of vertices v_0 = s, v_1, v_2, ..., v_k = t such that the edge (v_{i-1},v_i) is in E for all 1 \leq i \leq k . If G is acyclic, then its reachability relation is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction. A noteworthy consequence of this is that since partial orders are anti-symmetric, if s can reach t , then we know that t cannot reach s . Intuitively, if we could travel from s to t and back to s , then G would contain a cycle, contradicting that it is acyclic. If G is directed but not acyclic (i.e. it contains at least one cycle), then its reachability relation will correspond to a preorder instead of a partial order. Given a graph G , the algorithm begins by organizing the vertices into layers starting from an arbitrary vertex v_0 . The layers are built in alternating steps by first considering all vertices reachable from the previous step (starting with just v_0 ) and then all vertices which reach to the previous step until all vertices have been assigned to a layer. By construction of the layers, every vertex appears at most two layers, and every directed path, or dipath, in G is contained within two adjacent layers L_i and L_{i+1} . Let k be the last layer created, that is, the lowest value for k such that \bigcup_{i=0}^{k} L_i = V . The graph is then re-expressed as a series of digraphs G_0, G_1, \ldots, G_{k-1} where each G_i = r_i \cup L_i \cup L_{i+1} and where r_i is the contraction of all previous levels L_0 \ldots L_{i-1} into a single vertex. Because every dipath appears in at most two consecutive layers, and because each G_i is formed by two consecutive layers, every dipath in G appears in its entirety in at least one G_i (and no more than 2 consecutive such graphs) For each G_i , three separators are identified which, when removed, break the graph into three components which each contain at most 1/2 the vertices of the original. As G_i is built from two layers of opposed dipaths, each separator may consist of up to 2 dipaths, for a total of up to 6 dipaths over all of the separators. Let S be this set of dipaths. The proof that such separators can always be found is related to the Planar Separator Theorem of Lipton and Tarjan, and these separators can be located in linear time. For each Q \in S , the directed nature of Q provides for a natural indexing of its vertices from the start to the end of the path. For each vertex v in G_i , we locate the first vertex in Q reachable by v , and the last vertex in Q that reaches to v . That is, we are looking at how early into Q we can get from v , and how far we can stay in Q and still get back to v . This information is stored with each v . Then for any pair of vertices u and w , u can reach w via Q if u connects to Q earlier than w connects from Q . Every vertex is labelled as above for each step of the recursion which builds G_0 \ldots, G_k . As this recursion has logarithmic depth, a total of O(\log{n}) extra information is stored per vertex. From this point, a logarithmic time query for reachability is as simple as looking over each pair of labels for a common, suitable Q . The original paper then works to tune the query time down to O(1) . In summarizing the analysis of this method, first consider that the layering approach partitions the vertices so that each vertex is considered only O(1) times. The separator phase of the algorithm breaks the graph into components which are at most 1/2 the size of the original graph, resulting in a logarithmic recursion depth. At each level of the recursion, only linear work is needed to identify the separators as well as the connections possible between vertices. The overall result is O(n \log n) preprocessing time with only O(\log{n}) additional information stored for each vertex. Preprocessing performs the following steps. We add a new vertex s which has an edge to each 0-indegree vertex, and another new vertex t with edges from each 0-outdegree vertex. Note that the properties of G allow us to do so while maintaining planarity, that is, there will still be no edge crossings after these additions. For each vertex we store the list of adjacencies (out-edges) in order of the planarity of the graph (for example, clockwise with respect to the graph's embedding). We then initialize a counter i = n + 1 and begin a Depth-First Traversal from s . During this traversal, the adjacency list of each vertex is visited from left-to-right as needed. As vertices are popped from the traversal's stack, they are labelled with the value i , and i is then decremented. Note that t is always labelled with the value n+1 and s is always labelled with 0 . The depth-first traversal is then repeated, but this time the adjacency list of each vertex is visited from right-to-left. When completed, s and t , and their incident edges, are removed. Each remaining vertex stores a 2-dimensional label with values from 1 to n . Given two vertices u and v , and their labels L(u) = (a_1, a_2) and L(v) =(b_1, b_2) , we say that L(u) if and only if a_1 \leq b_1 , a_2 \leq b_2 , and there exists at least one component a_1 or a_2 which is strictly less than b_1 or b_2 , respectively. The main result of this method then states that v is reachable from u if and only if L(u) , which is easily calculated in O(1) time. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1365511647 under CC BY-SA 4.0; modifications have been made.