0
$\begingroup$

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

Labelled graph

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

max depth dfs

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.

min depth dfs

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)?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.