Parallel Complexity of Depth-First-Search and Maximal Path in Restricted Graph Classes

Depth First Search ($\mathrm{𝖣𝖥𝖲}$) is an archetypal graph algorithm that has played a pivotal role in the study of several problems such as biconnectivity, triconnectivity, topological sorting, strong connectivity, planarity testing and embedding etc. Along with Breadth First Search (BFS) it is perhaps one of the best known algorithms. However, while the BFS algorithm is easy to parallelize, no such deterministic parallel algorithm is known for $\mathrm{𝖣𝖥𝖲}$²²2When talking about parallel computation, we will mean the class $\mathrm{𝖭𝖢}$. In terms of PRAM models, a problem is said to be in the $\mathrm{𝖭𝖢}$ if there exists a PRAM machine and constants $k,c$ such that the machine solves the problem in $O$(log${}_{}{}^{k}n$) time, using $O$($n^c$) many parallel processors. If the machine is a Concurrent Read Concurrent Write PRAM, we denote this class by CRCW[${\log }^{k}n$]. An equivalent definition in terms of boolean circuits also exists. In particular CRCW[${\log }^{k}n$] is equivalent to ${\mathrm{𝖠𝖢}}^k$ (see [39, Section 3.4]).. In fact, Reif showed in the 1980’s [48] that unless all of $𝖯$ is parallelizable, there is no parallel algorithm that can mimic the familiar recursive $\mathrm{𝖣𝖥𝖲}$. To be slightly more precise finding the lexicographically first $\mathrm{𝖣𝖥𝖲}$-order is $𝖯$-complete. Roughly contemporaneously, the problem of finding a (not necessarily lexicographically first) $\mathrm{𝖣𝖥𝖲}$-order was reduced to the minimum weight perfect matching problem for bipartite graphs in [1] (and in [2] for directed graphs) which coupled with randomized parallel algorithm for min-weight perfect matching [40, 47], yielded a randomized parallel algorithm for $\mathrm{𝖣𝖥𝖲}$. Recent advances in matching algorithms [28] indeed yield a deterministic parallel algorithm for $\mathrm{𝖣𝖥𝖲}$ although using quasipolynomially many (in particular, $n^{O(\text{log }n)}$ many) processors.

A natural question to consider is: for which restricted graph classes can we give deterministic parallel algorithms for $\mathrm{𝖣𝖥𝖲}$. Planar graphs, as well as digraphs have been known to possess (deterministic) parallel $\mathrm{𝖣𝖥𝖲}$ algorithms dating back to half a century ago [53, 33, 35, 38, 37, 3]. Khuller also gave an $\mathrm{𝖭𝖢}$ algorithm for $\mathrm{𝖣𝖥𝖲}$ in $K_{3,3}$-minor-free graphs [41]. The above mentioned algorithms differ in their parallel complexity. For example Kao, Klein in [38] gave a parallel running time of $O({\log }^{10}n)$ for $\mathrm{𝖣𝖥𝖲}$ in planar digraphs while optimizing the number of required processors to be linear. More recently, Ghaffari et al [29] have given a (randomized) nearly work efficient algorithm for $\mathrm{𝖣𝖥𝖲}$ running in $\tilde{O}$($\sqrt{n}$) time and $\tilde{O}$($m+n$) work. Our metric for evaluating an algorithm is more complexity theoretic – so we try to optimise on the complexity class we can place the problem in. In particular, we are interested in placing the problems in the smallest possible class in the following (loose) hierarchy : $\text{L}\subseteq \mathrm{𝖴𝖫}\subseteq \mathrm{𝖭𝖫}\subseteq {\mathrm{𝖠𝖢}}^1\subseteq {\mathrm{𝖭𝖢}}^2\subseteq {\mathrm{𝖠𝖢}}^3\subseteq \mathrm{\dots }$ (See Chapter 6 of [9]).

Most algorithms for parallel $\mathrm{𝖣𝖥𝖲}$ in graphs proceed via finding a balanced path separator in the graph, which is a path such that removing all of its vertices leaves behind connected components (or strongly connected components in case of digraphs) of small size, allowing for logarithmic depth recursion. It was shown by Kao in [35] that all graphs and digraphs have balanced path separators, and it is easy to find one sequentially using the $\mathrm{𝖣𝖥𝖲}$ algorithm itself. The challenge thus is to find a path separator in parallel. Another useful result Kao [36, 37] also showed is that if we have a small number of disjoint paths that together constitute a balanced separator (by small we mean up to polylogarithmically many, we call these multi-path separators), then we can trim and merge them into a single balanced path separator in parallel. If we could somehow merge and reduce a multi-path separator consisting of a large number of paths, say $O$($n$) many, to a multi-path separator consisting of up to constant (or even polylogarithmically many) number of paths in $\mathrm{𝖭𝖢}$, then we would immediately have an $\mathrm{𝖭𝖢}$ algorithm for $\mathrm{𝖣𝖥𝖲}$, as the set of all vertices of the graph constitutes a trivial multi-path separator. Such a routine to reduce the number of paths in a multi-path separator is indeed the heart of the $\mathrm{𝖱𝖭𝖢}$ algorithm of Aggarwal and Anderson [1] (and also [2]), and this is where the randomized routine for minimum weight perfect matching in bipartite graphs is used.

We assume the reader is familiar with tree-decompositions, planarity, embeddings on surfaces and graph minors. When referring to concepts like treewidth, minors and genus of digraphs, we will always intend them to apply to the underlying undirected graph. In digraphs, we will use the term path to mean simple directed path unless otherwise stated. We will use tail of a path to refer to the starting vertex of the path and head of a path to refer to the ending vertex of the path. The term disjoint paths will always mean vertex disjoint paths, and the term internally disjoint paths will refer to paths that are disjoint except possibly sharing end points. In a given graph $G=(V,E)$ and edge $(u,v)\in E(G)$, we denote the graph obtained by removing the edge $(u,v)$ (but keeping the vertices $u,v$ intact) by $G-(u,v)$.

We refer the reader to [9] for definitions of classes $\text{L},\mathrm{𝖭𝖫},\mathrm{𝖠𝖢},\mathrm{𝖭𝖢}$. A nondeterministic Turing machine is said to be unambiguous if for every input, there is at most one accepting computation path. The class $\mathrm{𝖴𝖫}$ is the class of problems for which there exists an unambiguous Logspace Turing machine to decide the problem. In our setting, our outputs are not binary, but encodings of objects like a DFS tree, or a maximal path. Each of the classes mentioned above can be generalised to deal with functions instead of just languages in a natural way. One may refer to [34] or [3, Section 2] for more details, specially what is meant by the computation of functions by a bounded space class like L, $\mathrm{𝖭𝖫}$ or $\mathrm{𝖴𝖫}\cap \text{co-UL}$. In simplest terms, the output has a size of polynomially many bits and each bit can be computed in the stated class. We will often refer to a machine that computes a function as a transducer. A constant number of L transducers may be composed in L (see [9, Chapter 4]). A similar result holds for classes like $\mathrm{𝖭𝖫},\mathrm{𝖴𝖫}\cap \text{co-UL}$ (see [3, Section 2] for a more elaborate explanation).

An important result in the Logspace world is that of Reingold [49] which states that the problem of deciding reachability (as well as its search version) in undirected graphs is in L. Using this and the lemma of composition of L transducers, many routines like computing connected components left after removing some vertices, or counting the number of vertices in a connected component, can be shown to be in L. Another result we will use is that the problem of reachability in directed planar graphs is in UL $\cap$ co-UL, as shown by [13, Theorem 1.1]. This extends to graphs of bounded genus, and in fact to graphs of $O$(log $n$) genus if their polygonal schema is given as part of input [31, Theorem 7] (See also [43, 54, 19]). The theorem of [31] achieves this by giving a logspace algorithm to compute $O$(log $n$) size weight functions for edges that isolate shortest paths between vertices of the input graph. In other words, for any pair of vertices $u,v$, there is a unique path minimum weight path from $u$ to $v$ under the weight function computed by [31, Theorem 7]. Thierauf and Wagner [55] showed that with such path isolating weights assigned to edges, we can compute distances as well as shortest path between vertices, in UL $\cap$ co-UL. These results will be useful in computing arborescences⁴⁴4An arborescence of a digraph $G$ is a spanning tree rooted at a vertex $r$, such that all edges of the tree are directed away from $r$. in bounded genus graphs in Section 4.

Suppose $𝒞$ is a complexity class (a set of boolean functions). We use ${\mathrm{𝖠𝖢}}^k(𝒞)$ to denote functions that can be computed by a family of ${\mathrm{𝖠𝖢}}^k$ circuits augmented with oracle gates that can compute functions in $𝒞$. Note for example, that since $\text{UL }\cap \text{ co-UL}\subseteq {\mathrm{𝖠𝖢}}^1$, the class ${\mathrm{𝖠𝖢}}^1$(UL $\cap$ co-UL) is contained in ${\mathrm{𝖠𝖢}}^2$.

We will use the notion of Gaifman graph of a logical structure:

The treewidth of the structure is the treewidth of its Gaifman graph. We will use the following extension of Courcelle’s theorem by [25]:

We restate some of the existing algorithms and analyze their complexity with respect to circuits/space bounded complexity classes. First, we reiterate an algorithm of Kao (see also [35, 2, 37]) that combines a small number of path separators into a single path separator in parallel, and observe that it is in L given an oracle for $\mathrm{𝖱𝖤𝖠𝖢𝖧}$. We state the theorems and corollaries for digraphs, but the corresponding statements for undirected graphs also hold with appropriate changes.

We reproduce the proof for completeness in Section A.1.1. Note that as a corollary, the above algorithm is in $\mathrm{𝖭𝖫}$ for general directed graphs, and in UL $\cap$ co-UL for directed graphs of $O$(log $n$) genus (using [31]). For undirected graphs, the algorithm (with appropriate changes) is in $𝖫$ using Reingold’s algorithm [49]. As noted in [2, 38], if we have a multi-path separator consisting of $k$ many paths, say $\{P_1,P_2\mathrm{\dots }{P}_k\}$, we can combine them into a single path separator using $k$ iterations of the above procedure with $k$ transducers. Thus we have:

For bounded treewidth graphs, we can find a tree decomposition in L using [25, Theorem 1.1], and we know that there is always a bag in the tree decomposition of a graph whose vertices together form a $1/2$-separator of the graph. Since $\mathrm{𝖱𝖤𝖠𝖢𝖧}$ is known to be in L for digraphs of bounded treewidth (from Theorem 3), we have the following result:

It is shown in [3, Section 7] how to construct a DFS tree in a digraph given a routine for finding path separators, in parallel. The algorithm follows a divide and conquer strategy, where we find DFS trees on the smaller strongly connected components in parallel, and sew them together using a routine for DFS in DAGs. We state the result in the following proposition.

Although the proposition is for digraphs, the same idea works in the simpler setting of undirected graphs also (Instead of DAGs of strongly connected components, we just have to recurse on connected components there. See for example [53]). We will also use the following, more general notion of cycle separators in planar graphs, that was introduced in [45]:

Miller showed in [45] that such a weighted cycle separator always exists if $G$ is biconnected and if no face is too heavy. Moreover, we can find such a separator in parallel⁵⁵5The theorem in [45] also gives a bound on size of the separator but that is not important for us. (see also [52]).

We show how to find balanced path separators (and therefore a $\mathrm{𝖣𝖥𝖲}$ tree) in digraphs that can be embedded on a surface of genus at most a fixed constant $g$, in $\mathrm{𝖭𝖢}$. For an undirected graph, it is easy to see that a DFS tree of the bidirected version of it is also a DFS tree of the original graph.

The first step naturally is to find an embedding, which can be done using the theorem of Elberfeld and Kawarabayashi [26, Theorem 1], which states that we can find an embedding of a graph of genus at most a constant $g$, on a surface of genus $g$, in Logspace. The idea is to find a small number of disjoint, surface non-separating cycles (not necessarily directed cycles), say $C_1,C_2,\mathrm{\dots }{C}_l$ ($l\le g$) in $G$, such that the (weakly) connected components left after removing them are all planar. These can be found with at most $g$ sequential iterations. Then, if any of the remaining planar components has a large strongly connected component, we can find a $2/3$-path separator, say $P$, in it using [38, Theorem 19]. A more modern analysis of the algorithm in [38] gives a UL $\cap$ co-UL bound (see [15, Section 3.3] for a proof. See also [3, Lemma 50], which gives an $11/12$-path separator with the same bound). Then $C_1,C_2\mathrm{\dots }{C}_l,P$ together form a balanced multi-path separator of the digraph $G$. The (possibly undirected) cycles $C_1,C_2\mathrm{\dots }{C}_l$ will have an additional property. Any $C_i\in \{C_1,C_2\mathrm{\dots }{C}_l\}$ will either be a directed cycle, or it will consist of two internally disjoint (directed) paths that share a common tail vertex and a common head vertex. Therefore the multi-path separator can be written as consisting of at most $2g+1$ many paths, and we can use Corollary 6 to get the required path separator. We use the following known fact (see [46, Lemma 4.2.4] or [30, Fact 9.1.6]).

Therefore, if we have an algorithm to find such a (undirected) cycle in $\mathrm{𝖭𝖢}$, then we can repeat it $g$ times to find the required (undirected) cycles $C_1,C_2\mathrm{\dots }{C}_k$. We will use the following lemma from [5] (See also [56]) to find such cycles.

Clearly the theorem also works if we have an arborescence instead of a spanning tree. The fundamental cycle $C$ corresponding to a non-tree edge $e=(u,v)$ would consist of the non-tree edge $e$ and two vertex disjoint directed paths, say $P,P^{\prime }$, starting from a common ancestor of $(u,v)$ in the arborescence (we can include the common ancestor vertex in either of $P$ or $P^{\prime }$), and ending at $u,v$ respectively. We can find an arborescence in UL $\cap$ co-UL using [31, 55] (as explained in the appendix), and the required fundamental cycle in Logspace using the theorem of [26]. We describe the steps of the algorithm in detail in Section A.2. Therefore we can find a $2/3$-path separator in directed graphs of bounded genus in UL $\cap$ co-UL. Using Proposition 8, we can find a depth first search tree in such graphs in $\mathrm{𝖠𝖢}$¹(UL $\cap$ co-UL), finishing the proof of part 1 of Theorem 1.

We start with computing the $3$-clique-sum decomposition by the $\mathrm{𝖭𝖢}$ algorithm of [27]. We will denote this decomposition tree by $T_G$, each node of which is either a piece node or a clique node, and the weight of each node is the number of vertices in the corresponding piece/clique. (Note that by this convention, the sum of weights of all nodes of $T_G$ will sum up to more than $n$ since some vertices would occur in multiple pieces).

Such a node always exists and can be found in Logspace by traversing along the heaviest child in $T_G$ (see Chapter 7 of [18] for example). We will assume $t_R$ to be the root of $T_G$ hereafter. We will denote the subtrees of $T_G$ that are children of $t_R$ by $\{T_1,T_2,\mathrm{\dots }{T}_l\}$, the subgraphs of $G$ corresponding to these subtrees by $\{G_1,G_2,\mathrm{\dots }{G}_l\}$, and the cliques by which they are attached to $R$ by $\{c_1,c_2\mathrm{\dots }{c}_l\}$ respectively. These subgraphs might themselves consist of smaller subgraphs glued at the common clique. For example, $G_1$ might consist of $G_{11},G_{12},\mathrm{\dots }{G}_{1k}$ that are glued at the shared clique $c_1$ (i.e. $G_1=G_{11}{\oplus }_{c_1}{G}_{12}\mathrm{\dots }{\oplus }_{c_1}{G}_{1k}$). See Figure 3 for reference. Note that because $R$ is a central node, $\forall i\in [1..k]$. If $t_R$ is a clique node, then we have a $1/2$-separator of at most three vertices and we are done. Therefore there are two cases to consider. Either $R$ is a planar piece, or a piece of bounded treewidth.

The input graph $G$ can be seen as a structure $𝒜$ whose universe, $|𝒜|$ is $V(G)$, and its vocabulary consists of binary relation symbol $E$ which is interpreted as the edge relation $E(G)$ over $V(G)$. The Gaifman graph of $𝒜$, $G_{𝒜}$, is isomorphic to $G$. We will need to add a linear order $O$ on $|𝒜|$, which would amount to adding $|V(G)|$ many edges in $G_{𝒜}$. A known result in model theory (see [11, Lemma 1], also [17, Theorem VI.4]) is that we can add a linear order to a structure, such that the treewidth of the structure is increased by at most a constant. It is shown in [10, Lemma 5.2] that we can construct such a linear order in L. Therefore after computing the order $O$ and adding it to $𝒜$ the new structure ${𝒜}^{\prime }$ also has bounded treewidth. Moreover, for any two vertices $u,v$, we can query if $u$ is “lesser than” $v$ in the transitive closure of $O$, in logspace. We also add the edges $E(G)$ to our universe of discourse, as well as an incidence relations : $tail(e,v)$ which is true iff the edge $e\in E(G)$ has vertex $v$ as its tail, and $head(e,v)$ defined similarly. This can again be done without blowing up the treewidth (see section 6 of the full version).

We use to denote that vertex $u$ is lesser than vertex $v$ in the transitive closure of $O$. An ordering over vertices defines a unique lexicographically first DFS tree. The algorithm will go over each edge of $E$, and use Theorem 3 to query if it belongs to the lex-first DFS tree of $G$, in L. Our universe is $V\cup E$, and the relations on it given are $tail,head$, and the linear order $O$. To express the membership of an edge in the lex-first DFS tree with respect to $O$, we will use a theorem connecting the lex-first DFS tree to lex-first paths. We define lexicographic ordering on paths starting from a common vertex:

This naturally defines the notion of the lexicographically least path starting from $r$ and ending at a vertex $v$. We call it the lex-first path from $r$ to $v$. We use the following result which is shown in the proof of Theorem 11 in [23]:

Thus in order to check if an edge $(u,v)$ belongs to $T_l$ (rooted at $r$), it suffices to check if it is the last edge of the lex-min path in $G$ from $r$ to $v$. We define a formula ${\varphi }_{DFS}(u,v)$, which is true iff the edge $(u,v)$ is part of the lex-first DFS tree $T_l$. Thus the logspace algorithm is the following : For each edge $(u,v)$ in $E$, query ${\varphi }_{DFS}(u,v)$ and add to output tape iff the query returns yes. A DFS numbering or order of traversal of the vertices of $T_l$ can easily be obtained from $T_l$ by doing an Euler tree traversal of $T_l$ with respect to the ordering $O$. Now all that remains is to express the formula ${\varphi }_{DFS}(u,v)$ in $\mathrm{𝖬𝖲𝖮}$. We defer that to the full version.

In this section we will show that given a planar undirected graph $G$ and a vertex $r$ in it, we can find a maximal path in $G$ starting from $r$, in L. We will assume that our graph is embedded in a plane with a face marked as outer face (a planar embedding can be found in L by [6, 22]). The first step is to reduce the problem to that of finding a maximal path in a triconnected component of $G$ that is $3$-connected (i.e. it is not a cycle or a dipole). We decompose the graph into its triconnected components, which can be done in L as described in [20]. We can choose a leaf piece $L$ of this decomposition tree which is connected to its parent piece $H$ by separating pair, say $(r_0,r_1)$. The basic idea is to find a path from $r$ ($L$ is chosen such that it does not contain $r$) to one of the vertices of the separating pair, say $r_0$, without going through $r_1$. Then it suffices to find a maximal path in $L$ starting from $r_0$, that does not end at $r_1$. Some care must be taken in the reduction however, and cases like when $L$ is a simple cycle need to be handled. We defer the details of the reduction to the full version.