Minimizing/Maximizing recursion depth for DFS

Question

The idea for this problem comes from GATE CS 2014 Set-3 Q13.

Given a graph, are there any heuristics to figure out a DFS traversal which has minimum/maximum recursion depth?

Consider the graph from the question, labelled

Consider the DFS traversal a-b-c-f-e-d-g-h-i-j-k-l-m-n-q-p-o-r-s-t-u with a recursion depth of 19. The numbers represent the recursion depth as per the question

Now consider the traversal j-k-l-m-p-s-r-o-t-q-u-n-i-f-e-d-a-b-c-g-h, which has a recursion depth of 8.

While it is easy to figure this out for a small enough graph and on paper, I am struggling to find a well defined algorithm/heuristic to do so. My intuition in minimizing was to find an articulation point in the graph which would split it into the maximum number of subgraphs(hence j as a starting vertex), and for maximizing, a node with minimum degree which is not adjacent to an articulation point(hence discarding k and u and selecting a as starting vertex but any other similar vertex would do).

Is there a name for this problem, and any approaches to solve(other than brute force)?

Answer 1

Unfortunately, I think that that there is a reduction from the longest path problem, which have a $\mathsf{NP}$-complete decision version (finding the maximum depth is equivalent to finding the longest path between two vertices).

A possible approximation heuristic would be running a DFS from an arbitrary vertex, then running it again from the leaf farthest from the root in the traversal tree.

This post gives a dynamic programming exact algorithm for finding longest paths.