[PDF] [PDF] All-Pairs 2-Reachability in O( log n) Time - CORE

[PDF] Graph Reachability - HKUST CSE Dept

Graph Reachability Panagiotis Parchas Given a directed graph G and two nodes u and v, is there a path Directed Graph → DAG (directed acyclic graph) by

[PDF] Reachability is harder for directed than for undirected finite graphs

the reachability problem is harder for directed graphs than for undirected graphs simply “graph”, we mean either directed or undirected graph; when it is 

[PDF] All-Pairs 2-Reachability in O( log n) Time - CORE

In the 2-reachability problem we are given a directed graph G and we wish to determine if there are two (edge or vertex) disjoint paths from u to v, for given pair  

Chapter 6 GRAPH REACHABILITY QUERIES: A SURVEY

Graph reachability (or simply reachability) queries, to test whether there is a path from a node to another node in a large directed graph, have being studied [1 

[PDF] A Fully Dynamic Reachability Algorithm for Directed Graphs with an

The dynamic reachability problem, i e , the problem of maintaining a directed graph that undergoes a sequence of edge insertions and deletions in a way that  

[PDF] DFS & Directed Graphs

Strong connectivity Connected components in directed graphs defined based on mutual reachability Two vertices in a directed graph are mutually reachable if 

[PDF] An Efficient Reachability Indexing Scheme for Large Directed Graphs

Among them, graph reachability queries have attracted a lot of research attention Given two vertices u and v in a directed graph, a reachability query asks if there 

[PDF] directed writing igcse paper 2

[PDF] directeur france bleu sud lorraine

[PDF] directional selection

[PDF] directions to port canaveral cruise ships

[PDF] director appointment letter doc

[PDF] director's cut

[PDF] directors chair home depot

[PDF] directors chair replacement covers

[PDF] directors chair with side table

[PDF] directors chairs for sale

[PDF] directors guild of america basic agreement

[PDF] directors guild of america los angeles

[PDF] directors guild of america new york

[PDF] directors guild rules

[PDF] directors union

All-Pairs 2-Reachability inO(nωlogn)Time?

Loukas Georgiadis

1, Daniel Graf2, Giuseppe F. Italiano†3,

Nikos Parotsidis

4, and Przemysław Uznański5

1

Univ ersityof Ioannina, Ioannina, Greece

loukas@cs.uoi.gr 2 Departmen tof Computer Science, ETH Züric h,Züric h,Switzerland daniel.graf@inf.ethz.ch 3

Univ ersityof Rome T orV ergata,Roma, Italy

giuseppe.italiano@uniroma2.it 4

Univ ersityof Rome T orV ergata,Roma, Italy

nikos.parotsidis@uniroma2.it 5 Departmen tof Computer Science, ETH Züric h,Züric h,Switzerland przemyslaw.uznanski@inf.ethz.chAbstract In the2-reachability problem we are given a directed graphGand we wish to determine if there are two (edge or vertex) disjoint paths fromutov, for given pair of verticesuandv. In this paper, we present an algorithm that computes2-reachability information for all pairs of vertices inO(nωlogn)time, wherenis the number of vertices andωis the matrix multiplication exponent. Hence, we show that the running time of all-pairs2-reachability is only within alog factor of transitive closure. Moreover, our algorithm produces a witness (i.e., a separating edge or a separating vertex) for all pair of vertices where2-reachability does not hold. By processing these witnesses, we can compute all the edge- and vertex-dominator trees ofGinO(n2)additional time, which in turn enables us to answer various connectivity queries inO(1)time. For instance, we can test in constant time if there is a path fromutovavoiding an edgee, for any pair of query verticesuandv, and any query edgee, or if there is a path fromutovavoiding a vertex w, for any query verticesu,v, andw.

1998 ACM Subject ClassificationE.1 Graphs and Networks, F.2.2 Computations on Discrete

Structures, G.2.2 Graph Algorithms

Keywords and phrases2-reachability, All Dominator Trees, Directed Graphs, Boolean Matrix

Multiplication

Digital Object Identifier10.4230/LIPIcs.ICALP.2017.741Intro ductionTheall-pairs reachability problemconsists of preprocessing a directed graph (digraph)

G= (V,E)so that we can answer queries that ask if a vertexyis reachable from a vertexx. This problem has many applications, including databases, geographical information systems, social networks, and bioinformatics [11]. A classic solution to this problem is to compute the transitive closure matrix ofG, either by performing a graph traversal (e.g., depth-first or breadth-first search) once per each vertex as source, or via matrix multiplication. For a? A full version of the paper is available athttps://arxiv.org/abs/1612.08075.

Partially supported by MIUR, the Italian Ministry of Education, University and Research, under Project

AMANDA (Algorithmics for MAssive and Networked DAta). E A T C

S©Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis,and Przemysław Uznański;

licensed under Creative Commons License CC-BY

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017).

Editors: Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl;

Article No.74; pp.74:1-74:14

Leibniz International Proceedings in InformaticsSchloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

74:2 All-Pairs 2-Reachability inO(nωlogn)Timedigraph withnvertices andmedges, the former solution runs inO(mn)time, while the

latter inO(nω), whereωis the matrix multiplication exponent [4,13,17]. Here we study a natural generalization of the all-pairs reachability problem, that we refer to asall-pairs

2-reachability, where we wish to preprocessGso that we can answer fast the following type

of queries: For a given vertex pairx,y?V, are there two edge-disjoint (resp., internally vertex-disjoint) paths fromxtoy? Equivalently, by Menger"s theorem [15], we ask if there is an edgee?E(resp., a vertexz?V) such that there is no path fromxtoyinG\e(resp., G\z). We call such an edge (resp., vertex)separatingfor the pairx,y. One solution to the all-pairs2-reachability problem is to compute all the dominator trees ofG, with each vertex as source. The dominator tree ofGwith start vertexsis a tree rooted ats, such that a vertexvis an ancestor of a vertexwif and only if all paths fromstow includev[14]. All the separating edges and vertices for a pairs,v, appear on the path from stovin the dominator tree rooted ats, in the same order as they appear in any path froms tovinG. Given all the dominator trees, we can process them to compute the2-reachability information for all pairs of vertices (see Section 6). Since a dominator tree can be computed inO(m)time [2, 3], the overall running time of this algorithm isO(mn).

Our Results.

In this paper, we show how to beat theO(nm)bound for dense graphs. Specifically, we present an algorithm that computes2-reachability information for all pairs of vertices inO(nω)time in a strongly connected digraph, and inO(nωlogn)time in a general digraph. Hence, we show that the running time of all-pairs2-reachability is only within a logfactor of transitive closure. This result is tight up to alogfactor, since it can be shown that all-pairs2-reachability is at least as hard as computing the transitive closure, which is asymptotically equivalent to Boolean matrix multiplication [6]. Moreover, our algorithm produces a witness (separating edge or vertex) whenever2-reachability does not hold. By processing these witnesses, we can find all the dominator trees ofGinO(n2)additional time. Thus, we also show how to compute all the dominator trees of a digraph inO(nωlogn)time (inO(nω)time if the graph is strongly connected), which improves the previously known O(mn)bound for dense graphs. This in turn enables us to answer various connectivity queries inO(1)time. E.g., we can test inO(1)time if there is a path fromutovavoiding an edgee, for any pair of query verticesuandv, and any query edgee, or if there is a path fromutovavoiding a vertexw, for any query verticesu,v, andw. We can also report all the edges or vertices that appear in all paths fromutov, for any query verticesuandv.

Related Work.

To the best of our knowledge, ours is the first work that considers the all-pairs2-reachability problem and gives a fast algorithm for it. In recent work Georgiadis et al. [9] investigate the effect of an edge or a vertex failure in a digraphGwith respect to strong connectivity. Specifically, they show how to preprocessGinO(m+n)time in order to answer various sensitivity queries regarding strong connectivity inGunder an arbitrary edge or vertex failure. For instance, they can compute inO(n)time the strongly connected components (SCCs) that remain inGafter the deletion of an edge or a vertex, or report various statistics such as the number of SCCs in constant time per query (failed) edge or vertex. This result, however, cannot be applied for the solution of the2-reachability problem. The reason is that if the deletion of an edgeeleaves two verticesuandvin different SCCs inG\e, the algorithm of [9] is not able to distinguish if there is still a path or no path from utovinG\e. Previously, King and Sagert [12] gave an algorithm that can quickly answer sensitivity queries for reachability in a directed acyclic graph (DAG) [12]. Specifically, they show how to process a DAGGso that, for any pair of query verticesxandy, and a query

L. Georgiadis, D. Graf, G.F. Italiano, N. Parotsidis, and P. Uznański 74:3edgee, one can test in constant time if there is a path fromxtoyinG\e. Note that the

result of King and Sagert does not yield an efficient solution to the all-pairs2-reachability problem, since we needO(m)queries just to find if there is a separating edge for a single pair of vertices. Moreover, their preprocessing time isO(n3). Another interesting fact that arises from our work is that, somewhat surprisingly, computing all dominator trees in dense graphs is currently faster than computing a spanning arborescence from each vertex. The best algorithm for this problem is given by Alon et al. [1], who studied the problem of constructing a BFS tree from every vertex, and gave an algorithm that runs inO(n(3+ω)/2)time.

Our Techniques.

Our result is based on two novel approaches, one for DAGs and one for strongly connected digraphs. For DAGs we develop an algebra that operates on paths. We then use some version of1-superimposed coding to apply our path algebra in a divide and conquer approach. This allows us to use Boolean matrix multiplication, in a similar vein to the computation of transitive closure. Unfortunately, our algebraic approach does not work for strongly connected digraphs. In this case, we exploit dominator trees in order to transform a strongly connected digraphGinto two auxiliary graphs, so as to reduce

2-reachability queries inGto1-reachability queries in those auxiliary graphs. This reduction

works only for strongly connected digraphs and does not carry over to general digraphs. Our

algorithm for general digraphs is obtained via a careful combination of those two approaches.2Prelimina ries

We assume that the reader is familiar with standard graph terminology, as contained for instance in [5]. LetG= (V,E)be a directed graph (digraph). Given an edgee= (x,y)inE, we denotex(resp.,y) as thetail(resp.,head)ofe. Adirected pathinGis a sequence of verticesv1,v2,...,vk, such that edge(vi,vi+1)?Efori= 1,2,...,k-1. The path is said to contain vertexvi, fori= 1,2,...,k, and edge(vi,vi+1), fori= 1,2,...,k-1. Thelength of a directed path is given by its number of edges. As a special case, there is a path of length

0from each vertex to itself. We writeu vto denote that there is a path fromutov, and

u? vif there is no path fromutov. Adirected cycleis a directed path, with length greater than0, starting and ending at the same vertex. Adirected acyclic graph(in shortDAG) is a digraph with no cycles. A DAG has atopological ordering, i.e., a linear ordering of its vertices such that for every edge(u,v),ucomes beforevin the ordering (denoted byu < v). A digraphGisstrongly connectedif there is a directed path from each vertex to every other vertex. Thestrongly connected componentsof a digraph are its maximal strongly connected subgraphs. Given a subset of verticesV??V, we denote byG\V?the digraph obtained after deleting all the vertices inV?, together with their incident edges. Given a subset of edgesE??E, we denote byG\E?the digraph obtained after deleting all the edges inE".

2-Reachability and 2-Reachability closure.

We writeu 2ev(resp.,u 2vv) to denote that

there are twoedge-disjoint(resp., internallyvertex-disjoint) paths fromutov, andu? 2ev (resp.,u? 2vv) otherwise. As a special case, we assume thatv 2ev(resp.,v 2vv) for each vertexvinG. We define an abstract setE+=E? {?,?}. The semantic of this set is as follows:e?Ecorresponds to an edgeeseparating two vertices,?corresponds to 2e(there is no single separating edge) and?corresponds to? (there is no path). Given a digraphG,ICALP 2017

74:4 All-Pairs 2-Reachability inO(nωlogn)Timeacbde

?????(a,b) (a,b) (a,b) (a,b) (b,c)?(b,c)?(d,e) (c,a) (c,a)? ?(d,e) ? ? ? ?(d,e) ????Figure 1A graph and its (not unique)2-reachability closure matrix. we define a2-reachability closureofG, denoted byG 2e, to be a matrix such that: G

2e[u,v]def=?

???ifu 2ev ?ifu? v

ewhereeis any separating edge foruandv.Sincev 2evfor eachv?V,G 2e[v,v] =?. An example of a graph with a2-reachability

closure matrix is given in Figure 1. Note that a 2-reachability closure matrix is not necessarily unique, as there might be multiple separating edges for a given vertex pair. We define the

2-reachability left closureG 2eLby replacingany separating edgewithfirst separating edge

and the2-reachability right closureG 2eRby replacing it withlast separating edge. Note that if there is only one edge separatinguandv, thenG 2e[u,v] =G 2eL[u,v] = G 2eR[u,v]. Given any 2-reachability closure matrix, one can compute efficiently the 2- reachability left and right closure matrices. We sketch below the basic idea for the left closure (the right closure is completely symmetric). Letuandvbe any two vertices. If G 2e[u,v]is either?or?, thenG 2eL[u,v] =G 2e[u,v]. Otherwise, letG 2e[u,v] = (x,y): ifu 2ex(i.e., ifG 2e[u,x] =?) then(x,y)is the first separating edge foruandvand G 2eL[u,v] = (x,y); otherwise,u? 2ex(i.e.,G 2e[u,x]?=?) andG 2eL[u,v] =G 2eL[u,x].

We show how to computeG 2eLandG 2eRfromG 2ein a total ofO(n2)worst-case time.3All-pairs 2-reachabilit yin D AGs

In this section we present ourO(nωlogn)time algorithm for all-pairs2-reachability in DAGs. The high-level idea is to mimic the way Boolean matrix multiplication can be used to compute the transitive closure of a graph: recursively along a topological order, combine the transitive closure of the first and the second half of the vertices in a single matrix multiplication. However, while in transitive closure for each pair(i,j)we have to store only information on whether there is a path fromitoj, for all-pairs2-reachability this is not enough. First, we describe a path algebra, used by our algorithm to operate on paths between pairs of vertices in a concise manner. We then continue with the description of a matrix product-like operation, which is the backbone of our recursive algorithm. Finally, we show how to implement those operations efficiently using some binary encoding and decoding at every step of the recursion. Before introducing our new algorithm, we need some terminology. LetG= (V,E)be a DAG, and letE1,E2be a partition of its edge setE,E=E1?E2. We say that a partition is anedge splitif there is no triplet of verticesx,y,zinGsuch that(x,y)?E2and(y,z)?E1 simultaneously. Informally speaking, under such split, any path inGfrom a vertexuto a vertexvconsists of a sequence of edges fromE1followed by a sequence of edges from E2(as a special case, any of those sequences can be empty). We denote the edge split by G= (V,E1,E2)(See Figure 2). We say that vertexxinG= (V,E1,E2)is on theleft(resp., right)sideof the partition ifxis adjacent only to edges inE1(resp.,E2). We assume without loss of generality that the vertices ofGare given in a topological orderingv1,v2,...,vn. L. Georgiadis, D. Graf, G.F. Italiano, N. Parotsidis, and P. Uznański 74:5 E 1 E 2 P 1 Q 1 v 1 v n v 2 P 2 Q 2 uvP n Q n v 3 v 4 Q 4 P

3Figure 2An edge split of a DAGG= (V,E1,E2).

3.1 Algebraic approach

Consider a family of pathsP={P1,P2,...,P?}, all sharing the same starting and ending verticesuandv. We would like to distinguish between the following three possibilities: (i)P is empty; (ii) at least one edgeebelongs to every pathPi? P; or (iii) there is no edge that belongs to all paths in (nonempty)P. To do that, we define therepresentationrepr(P): repr(P)def=?? i=1P i=? ??UifP=∅ ∅if no edge belongs to allPi whereUdenotes the top symbol in the Boolean algebra of sets (i.e., the complement of∅). We also define aleft representationreprL(P)?E+, whereE+=E? {?,?}, as follows: repr

L(P)def=?

?????ifP=∅ ?if no edge belongs to allPi in the topological order Aright representationreprR(P)?E+is defined symmetrically toreprL(P), by replacing minimumwithmaximum. IfreprL(P)?E(resp.,reprR(P)?E), we say thatreprL(P) (resp.,reprR(P)) is thefirst(resp.,last)common edgeinP. Note that ifPis the set ofall the pathsfromutov, thenrepr(P)contains all the information aboutG 2e[u,v]. Additionally, G 2eL[u,v] =reprL(P)andG 2eR[u,v] =reprR(P). With a slight abuse of notation we also say thatG 2e[u,v]?repr(P).

IObservation 1.

LetG= (V,E1,E2)be an edge split of a DAG, and letuandvbe two Qi={Q?E2:Qis a path fromvitov}(See Figure 2) and letSbe the family of all paths fromutov. Then:repr(S) =?n i=1? repr(Pi)?repr(Qi)? A straightforward application of Observation(1)yields immediately a polynomial time algorithm for computingG 2e. However, this algorithm is not very efficient, since the size ofrepr(P)can be as large as(n-1). In the following we will show how to obtain a faster algorithm, by replacingrepr(P)with a suitable combination ofreprL(P)andreprR(P). We next define two operations, denoted asserialandparallel. Although those operations are formally defined onE+=E? {?,?}, they have a more intuitive interpretation asICALP 2017

74:6 All-Pairs 2-Reachability inO(nωlogn)Timeoperations on path families. We start with the serial operation?. Fora,b?E+, we define:

a?bdef=?(?,?)ifa=?orb=?quotesdbs_dbs17.pdfusesText_23