Parallel Complexity of Depth-First-Search and Maximal path

Archit Chauhan, Samir Datta, M. Praveen · 2025

Read Parallel Complexity of Depth-First-Search and Maximal path by Archit Chauhan, Samir Datta, M. Praveen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-14974.txt.

Introduction

Archit Chauhan, Samir Datta, and Praveen study fast parallel methods for depth-first search in a 2025 paper. Building a depth-first tree is a basic graph task, yet its parallel cost stays unsettled after decades. Early work showed one ordered form resists fast parallel methods.

The authors give deterministic parallel algorithms for graphs of bounded surface complexity and for graphs avoiding a fixed minor. For graphs of bounded tree-width, they tighten the bound to logspace. They also improve the known bound for building a maximal path in flat graphs. The results push parallel graph theory closer to the general case, which remains open.

Catalog record

CREATORArchit Chauhan, Samir Datta, M. Praveen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-14974

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Parallel Complexity of Depth-First-Search and Maximal path Archit Chauhan, Samir Datta, M. Praveen Abstract Constructing a Depth First Search (DFS) tree is a fundamental graph problem, whose parallel complexity is still not settled. Reif showed parallel intractability of lex-first DFS. In contrast, randomized parallel algorithms (and more recently, deterministic quasipolynomial parallel algorithms) are known for constructing a DFS tree in general (di)graphs. However a deterministic parallel algorithm for DFS in general graphs remains an elusive goal. Working towards this, a series of works gave deterministic NC algorithms for DFS in planar graphs and digraphs. We further extend these results to more general graph classes, by providing NC algorithms for (di)graphs of bounded genus, and for undirected H H -minor-free graphs where H H is a fixed graph with at most one crossing. For the case of (di)graphs of bounded tree-width, we further improve the complexity to a Logspace bound. Constructing a maximal path is a simpler problem (that reduces to DFS) for which no deterministic parallel bounds are known for general graphs. For planar graphs a bound of O O (log n n ) parallel time on a CREW PRAM (thus in NC 2 ) is known. We improve this bound to Logspace. Department of Computer Science and Engineering, IIT Bombay, [email protected] Chennai Mathematical Institute, [email protected] Chennai Mathematical Institute, [email protected] We would like to thank the reviewers for their insightful suggestions and corrections which have significantly improved this paper. ccs Theory of computation Design and analysis of algorithms ccs Theory of computation Computational complexity and cryptography Circuit complexity keywords Parallel Complexity, Graph Algorithms, Depth First Search, Maximal Path, Planar Graphs, Minor-Free, Treewidth, Logspace † † runningauthor: A. Chauhan and S. Datta and M. Praveen † † copyright: Archit Chauhan, Samir Datta, M. Praveen 1 Introduction Depth First Search ( \mathsf{DFS} ) in undirected graphs is an archetypal graph algorithm whose origin is in the 19-th century work of Trémaux [ 27 ] [Chapter 3]. The {\mathsf{DFS}} algorithm 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 \mathsf{DFS} 1 1 1 When talking about parallel computation, we will mean the class \mathsf{NC} . In terms of PRAM models, a problem is said to be in the \mathsf{NC} 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 C oncurrent R ead C oncurrent W rite 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 {\mathsf{AC}}^{k} (see [ 39 , Section 3.4] ). . In fact, Reif showed in the 1980’s [ 49 ] that unless all of {\mathsf{P}} is parallelizable, there is no parallel algorithm that can mimic the familiar recursive \mathsf{DFS} . To be slightly more precise finding the lexicographically first {\mathsf{DFS}} -order is {\mathsf{P}} -complete. Roughly contemporaneously, the problem of finding a (not necessarily lexicographically first) {\mathsf{DFS}} -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 , 48 ] , yielded a randomized parallel algorithm for {\mathsf{DFS}} . Recent advances in matching algorithms [ 28 ] indeed yield a deterministic parallel algorithm for {\mathsf{DFS}} although using quasipolynomially many (in particular, n^{O(\textsf{log }n)} many) processors. Faced with the quest of finding a deterministic parallel algorithm (with polynomially many processors) for {\mathsf{DFS}} , a natural question is: for which restricted graph classes can we, in fact, parallelize {\mathsf{DFS}} . Planar graphs, as well as digraphs have been known to possess (deterministic) parallel {\mathsf{DFS}} algorithms dating back to half a century ago [ 55 , 32 , 35 , 38 , 37 , 3 ] . Khuller also gave an {\mathsf{NC}} algorithm for {\mathsf{DFS}} 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 {\mathsf{DFS}} 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 \mathsf{DFS} 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 : \mbox{{\sf L}}\subseteq{\mathsf{UL}}\subseteq{\mathsf{NL}}\subseteq{\mathsf{AC}}^{1}\subseteq{\mathsf{NC}}^{2}\subseteq{\mathsf{AC}}^{3}\subseteq\ldots (See Chapter 6 of [ 9 ] ). Most algorithms for parallel \mathsf{DFS} 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 {\mathsf{DFS}} 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 \mathsf{NC} , then we would immediately have an \mathsf{NC} algorithm for \mathsf{DFS} , 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 \mathsf{RNC} 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 also remark that in the literature of separators, an aspect of focus is often to minimize the size of the separator [ 44 , 46 ] . For our purpose of constructing a DFS tree, the length of the path/cycle separator is not important. 1.1 Our contributions We first look at graphs of bounded genus in section 4 , which are a natural generalization of planar graphs (planar graphs have genus zero), and show that \mathsf{DFS} is in \mathsf{NC} for such graphs. We are not aware of any deterministic {\mathsf{NC}} algorithm for \mathsf{DFS} even for toroidal

Read the complete text