Find longest path in graph with N nodes and N edges

Question

We have given weighted undirected connected graph with $n$ nodes and $n$ edges, we want to find the longest path in it. Note that the path should be in each node at most once. Since the graph has $n$ edges clearly it has exactly 1 cycle, and removing 1 edge from this cycle will lead us to a tree.

Clearly we can iterate over all edges of the cycle and run dijkstra to find this path in tree. But this has complexity of $O(N^2)$ in worse case if the whole graph is cycle. I was thinking that greedy solution that we should remove always the edge with lowest weight that lies on the cycle. How to prove this greedy solution, is it correct at all?

Answer 1

I know this is not what you are asking, but in fact there is an efficient algorithm.

This kind of graph problem can be solved in linear time on classes of bounded tree-width. The graphs you describe are a special case of tree-width $2$. Instead of going into the details of tree-width, I will describe the algorithm for the present problem.

We are working with segments of the cycle. Say, such a segment starts at vertex $s$ and ends in vertex $e$. The avenue $A$ of that segment is the segment together with all trees rooted at it. Unless the segment is the full cycle, $A$ is the respective connected component of (the graph minus (the cycle minus the segment)).

For each segment, we define $5$-tuple of numbers, called the type of the segment. It contains

• the length of the path from $s$ to $e$,
• the length of the longest path fully contained in $A$ that starts at $s$,
• the length of the longest path in $A$ that ends in $e$,
• the longest combined length of a disjoint pair of paths such as in the previous two lines, and
• the length of the longest path in $A$.

The key observation is that the type of the concatenation of two segments only depends on the types of the individual segments. Algorithmically, the respective operation on types can be done in $O(1)$. Thus, the overall algorithm works as follows:

1. Compute the type of each singleton segment.
2. Choose some point $s$ on the cycle.
3. Iteratively compute the types of all segments starting at $s$ by concatenating singletons.
4. The last such segment spans the whole cycle and the answer can be derived from its type.

Depending on the way your graph is represented as a data structure, the algorithm can be as fast as $O(n)$.

Answer 2

The greedy solution is not correct.

Let me construct a graph with $5$ vertices, $A$, $B$, $C$, $D$, $E$.

$AB$ is an edge with weight $1$.

$BC$ is an edge with weight $2$.

$AC$ is an edge with weight $2$.

$AD$ is an edge with weight $100$.

$CE$ is an edge with weight $100$.

The longest (heaviest) path is $DABCE$ with weight $203$. After removing $AB$, which is the lightest edge of the cycle $ABC$, the longest path is $DACE$ with weight $202$.

Answer 3

This can be solves in O(N) using sliding window maximum. First, locate the cycle in the graph and for each node on the cycle, use DP on tree to find the diameter of the tree and longest distance to it's leaf.

Now there are 2 cases for the longest simple path

1) The longest simple path is the longest diameter of each trees on the cycle.

2) The longest simple path is sum of the longest distance to the leaf of 2 nodes and the length between them on the cycle. Use sliding window maximum with the size equal to the number of nodes in the cycle to find the answer to this case.

The answer to this problem is the maximum value between these 2 cases.