0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Your graph could be the union of a clique and an independent set. You only know it's a cycle if it is connected. If it is a cycle, as you say, the longest path corresponds to removing the lightest edge. This is not too hard to prove, so I suggest you give it a try. $\endgroup$ – Yuval Filmus Apr 3 '18 at 9:06
  • $\begingroup$ I forgot to add upper that the graph will be always connected, also how can we find all the edges that are being part of this one cycle. $\endgroup$ – someone12321 Apr 3 '18 at 10:23
  • $\begingroup$ How you can find all the edges depends on how the graph is given to you, which you haven't specified. $\endgroup$ – Yuval Filmus Apr 3 '18 at 10:32
  • $\begingroup$ Sorry again about my post, since the graph can be big, it will be given as adjacent list, array of vectors in c++ $\endgroup$ – someone12321 Apr 3 '18 at 13:24
  • $\begingroup$ The adjacency lists allow you to go over all edges in $O(N)$. $\endgroup$ – Yuval Filmus Apr 3 '18 at 13:25
2
$\begingroup$

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)$.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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