Algorithm Problem: Find the longest elementary cycle in a directed graph

Question

The problem is: given a directed graph, find the longest simple cycle in the graph. I've searched the question and found this link Finding the longest cycle in a directed graph using DFS. The answer explains this is an NP hard problem.

But I'm confused by the following algorithm, it seems to run in O(|V| + |E|) time because we visit each edge exactly once.

maintain the following variables:

(1) global max: the length of the longest cycle in the graph.
(2) Map<GraphNode, Integer> cache: stores length of the longest cycle starting from the key node.
(3) Map<GraphNode, Integer> pathVisited: stores the node visited on the path and the corresponding step number. For example, A -> B -> C -> A, if starts from A, the Map will look like {A -> 1, B -> 2, C -> 3}, and when enters A again, the step becomes 4, and thus the length of cycle is 4 - 1 = 3
(4)Set<GraphNode> visited: contains the graphNodes that have been fully explored.

dfs(GraphNode cur, int curStep, Set<GraphNode> visited, Map<GraphNode, Integer> cache, Map<GraphNode, Integer> pathVisited):
    if visited.containsKey(cur), then 
        return // if the node have been explored, no need to explore again
    // if see a cycle, update the results(cache)
    if pathVisited.containsKey(cur), then 
       newCycleLen = curStep - pathVisited.get(cur)
       cache.put(cur, max {newCycleLen, cache.get(cur)})
       return 
    // no cycle yet, continue the search
    pathVisited.put(cur, curStep)
    for each neighbor of cur:
       dfs(neighbor, curStep + 1, cache, pathVisited)
    endfor
    visited.add(cur); // current node have been explored, in the future no need to visit it again.
    path.remove(cur)

I feel the above algorithm can solve the problem in O(|V| + |E|) time, because after fully exploring one node, we won't start dfs on that node again.

Can anyone give me some hint on why the above algorithm is wrong?

@n.m. yeah some test cases pass, but based on templatetypedef's example the algorithm will fail. — Patrick
– Patrick, Commented Dec 20, 2018 at 19:10

templatetypedef · Accepted Answer · 2018-12-18 02:30:32Z

1

Consider the following graph:

     D -- A
   / |    |
  E  |    |
   \ |    |
     C -- B

Now, imagine you start your DFS at node A and visit the nodes in the order B, then C, then D, and then E. Unless I've misinterpreted what your code is doing, I don't believe that this visitation order will allow you to discover the longest cycle A, B, C, E, D, A, since once you've visited D you've assigned it the wrong depth and cut off the path back to A.

answered Dec 18, 2018 at 2:30

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Patrick Over a year ago

Thanks for the answer! Just to make sure, the algorithm is wrong in this case because the longest cycle should be of length 5 (A -> B-> C -> E -> D -> A), however, if we visit the graph in the order A->B->D->E, i.e. visit D before E, then via E we will not be able to go back to A because D has been fully explored, so never get the correct answer.

Hai · Accepted Answer · 2018-12-18 03:46:45Z

0

I think problem is what is "elementary cycle". DFS is good if cycle have all point visited once time. But This is problem:

A---B
|\ /|
| E |
|/ \|
C---D

Assume direction:

A -> B

B -> D,E

C -> D

D -> E,A

E -> C

DFS will find longest cycle is 5, A->B->E->C->D->A but longest cycle should be A->B->E->C->D->E->A. Maybe you should try with new view

answered Dec 18, 2018 at 3:46

Hai

831 silver badge10 bronze badges

1 Comment

n. m. could be an AI Over a year ago

ABECDEA is not a simple cycle.

Collectives™ on Stack Overflow

Algorithm Problem: Find the longest elementary cycle in a directed graph

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related