Longest path in a graph

Question

Given a undirected graph with vertices form 0 to n-1, write a function that will find the longest path (by number of edges) which vertices make an increasing sequence.

What kind of approach would you recommend for solving this puzzle?

Answer 1

I would do a Dynamic Programming algorithm. Denote L(u) to be the longest valid path starting at node u. Your base case is L(n-1) = [n-1] (i.e., the path containing only node n-1). Then, for all nodes s from n-2 to 0, perform a BFS starting at s in which you only allow traversing edges (u,v) such that v > u. Once you hit a node for which you've already started at (i.e., a node u such that you've already computed L(u)), L(s) = longest path from s to u + L(u) out of all possible u > s.

The answer to your problem is the node u that has the maximum value of L(u), and this algorithm is O(E), where E is the number of edges in your graph. I don't think you can do faster than this asymptotically

EDIT: Actually, the "BFS" isn't even a BFS: it's simply traversing the edges (s,v) such that v > s (because you have already visited all nodes v > s, so there's no traversal: you'll immediately hit a node you've already started at)

So actually, the simplified algorithm would be this:

longest_path_increasing_nodes():
    L = Hash Map whose keys are nodes and values are paths (list of nodes)
    L[n-1] = [n-1] # base case
    longest_path = L[n-1]
    for s from n-2 to 0: # recursive case
        L[s] = [s]
        for each edge (s,v):
            if v > s and length([s] + L[v]) > length(L[s]):
                L[s] = [s] + L[v]
        if length(L[s]) > length(longest_path):
            longest_path = L[s]
    return longest_path

EDIT 2022-03-01: Fixed typo in the last if-statement; thanks user650654!

Answer 2

You can transform the original graph into a Directed Acyclic Graph by replacing each of the (undirected) edges by a directed edge going towards the node with bigger number.

Then you end up with this: https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/