Lower Bounds for Lexicographical DFS Data Structures
Sankardeep Chakraborty, Christian Engels · 2022
Depth-first search (DFS) is a very well-known graph traversal method which confers a number of structural properties that causes DFS to have numerous applications. These properties are captured in the DFS tree (forest), and are used to design efficient algorithms for many basic and fundamental algorithmic graph problems, namely, biconnectivity, 2-edge connectivity, topological sorting and planarity testing among many others. Recently, Chakraborty and Sadakane (MFCS 2019) studied the problem of compactly indexing the lexicographic DFS tree, and they showed various applications of this by designing an efficient index for shortest path, strongly connected component etc. Here, lexicographical means that the DFS algorithm chooses at every step the vertex that is unvisited and smallest in the lexicographical order of the vertices. Chakraborty and Sadakane presented their solution in two well-known models: The indexing and encoding models. In the indexing model, we wish to build an index$I$after preprocessing the input graph$G$such that queries can be answered using both$I$and$G$whereas in the encoding model, we seek to build a data structure$E$after preprocessing$G$such that the following queries have to be answered using only$E, (\mathrm{i})$return true if$t_{1}$is visited before$t_{0}$in the lexicographic DFS tree$T$rooted at$s$, and false otherwise, and (ii) return the number of children of any given node$v\in T$.