Longest Simple Path In Sparse Cyclic Graphs

Question

Given: An unweighted, directed Graph (G=(E,V)), which can contain any number of cycles.

Goal: For all vertices I want the longest simple path to some target vertex X in V

Algorithm Idea:

For each v in V
  v.distanceToTarget = DepthFirstSearch(v)
Next

DepthFirstSearch(v as Vertex)
  if v = target then
    'Distance towards target is 0 for target itself
    return 0
  elseif v.isVisitedInCurrentDFSPath then
    'Cycle found -> I wont find the target when I go around in cycles -> abort
    return -infinity
  else
    'Return the maximum Distance of all Successors + 1
    return max(v.Successors.ForEach(Function(v) DepthFirstSearch(v) )) + 1
  end if

Is this correct for all cases? (Assuming, that the target can be reached from every vertex)

The number of edges in my graphs is very small. Assume |E| <= 3*|V| holds. How would I compute the average time complexity?

Thanks!

Pauli Nieminen Pauli Nieminen · Accepted Answer · 2016-10-22T13:09:58

Time complexity is about what values influence your runtime most. In your case your evaluating all possible paths between v and target. That is basically O(number of routes). Now you need to figure out how to express number of all possible routes in terms of E and V.

Most likely result with be something like O(exp(E)) or O(exp(V)) because number of routes going through each node/vertex goes exponentially when you add new possible routes.

EDIT: I missed a detail that you were asking for average time complexity that would mean amortized complexity. But as your algorithm is always evaluates all possible routes worst case complexity is same as average complexity.

Longest Simple Path In Sparse Cyclic Graphs

1 Answers