9

I know that the longest path problem is NP-hard for a general graph. However, I am considering a particular kind of graph, consisting of one cycle, plus one additional edge incident on each vertex of the cycle. For example, for a cycle of length 7, we have the graph:

graph

All the edges are weighted (the weight is a real number and can be positive or negative). I want to find the largest simple path on this graph, where the size of a path is the sum of the weights of the edges on the path.

The algorithm should be linear in the size of the cycle. But any ideas are appreciated.

a06e
  • 18,594
  • 33
  • 93
  • 169
  • Surely this is a case of pruning dead-ends from the graph, then finding the edge with the lowest weight and using its two ends as the start- and end-points of the longest (highest-weighted) chain. – paddy Jan 09 '13 at 02:26
  • @paddy: That would work if weights couldn't be negative... – Oliver Charlesworth Jan 09 '13 at 02:27
  • @paddy: I don't understand very well. Can you be more specific? – a06e Jan 09 '13 at 02:31
  • @OliCharlesworth: I don't think that positive weights is a necessary restriction. After all, I can always add a large enough constant weight to all the edges, so that all weights become positive, without changing the problem. – a06e Jan 09 '13 at 02:33
  • 1
    @becko: That *will* change the problem; the offset on the result would be proportional to the number of edges in the path. – Oliver Charlesworth Jan 09 '13 at 02:34
  • Changing the weights by adding a constant (to each weight) *does* change the problem. – Daniel Brückner Jan 09 '13 at 02:35
  • @OliCharlesworth: You are right! I missed that. – a06e Jan 09 '13 at 02:35
  • @beck The `O(N^2)` algorithm is relatively straightforward, but I assume that you have it down already, right? – Sergey Kalinichenko Jan 09 '13 at 03:29
  • @dasblinkenlight: Yeah. Just check the pairs. Thanks anyway. – a06e Jan 09 '13 at 03:39
  • 1
    @becko Well, the naive algo that checks the pairs would be `O(N^3)`. You need to preprocess the cycle to get the distance between two points in `O(1)`. – Sergey Kalinichenko Jan 09 '13 at 03:42
  • @dasblinkenlight: I know. One could store in each vertex a partial sum of the weights through the cycle up to that vertex, starting at an arbitrary vertex of the cycle. Then the distance between two vertices in the cycle is simply the value stored at one vertex minus the value stored at the other vertex. I haven't really thought all the details because I've been focusing on finding a linear algorithm. But I think that's the idea. – a06e Jan 09 '13 at 03:51
  • @becko: I've expanded (or perhaps what I said is what you meant) what you've said to allow for doing it in linear time. However, I doubt you can get an exact answer that way. I think you're stuck with O(N^2) or maybe O(N log N) if you want an exact answer. – Nuclearman Jan 09 '13 at 05:22

3 Answers3

6

This could be reduced to Maximum subarray problem and solved in linear time.

  1. Disconnect the cycle (at any node).
  2. Append second copy of the remaining graph to the point where cycle was disconnected (we may skip the last node).
  3. Apply modified Kadane's algorithm to the resulting list of nodes.
  4. If the found path has no edges, search greatest-weight edge in the graph. If this edge has non-negative weight, report this single-edge path. If not, report this single-edge path anyway if empty paths are not allowed, or report empty path if they are allowed.

original graph -> modified graph

Necessary Kadane's algorithm modifications:

  1. Keep track of the number of nodes in current path (subarray). Trim nodes from tail when subarray has N or more "cycle" nodes. To trim these nodes efficiently, we need a queue that can report minimum value of its elements. Push elements to this queue wherever head of the path is advanced (add leaf edge weight if non-negative), pop elements when tail of the path is trimmed, and reset the queue wherever current path is reset to empty path. This queue contains prefix lengths of (not necessarily simple) path, where minimum value gives proper position to advance tail of the path. Such a queue may be implemented either as a deque holding only non-decreasing values, or as a pair of stacks as mentioned in this answer.
  2. Reset path length to max(0, leaf_edge_weight) wherever length of current path is below zero (instead of resetting it to zero as in original Kadane's algorithm).
  3. Add non-negative leaf edge weight (corresponding to head node) when current (non-empty) path is compared to the best-so-far path.
Community
  • 1
  • 1
Evgeny Kluev
  • 24,287
  • 7
  • 55
  • 98
  • I was also preparing an answer like this :) But the part that I haven't worked out is how to efficiently trim nodes from the tail when the subarray has more than N nodes. Could you elaborate? – j_random_hacker Jan 09 '13 at 12:13
  • @j_random_hacker: This part definitely needed more explanations. Thanks. – Evgeny Kluev Jan 09 '13 at 13:46
0

The longest path is almost certainly between two of the outer vertices. It is also almost certainly necessary to cover all of the vertices in the cycle.

Thus you want to use DFS to map out the cycle in O(N). Then calculate the length of the current cycle arrangement. Add to that length the distance from the first point in the cycle to it's outer, and the last point to it's outer. And that gives you the actual path length, which you store separately from the cycle length.

Increase the index of the first point and the last point (can be done in O(1)), remove the length of the edge that now goes directed from the first to last point. Then add the outer lengths again. Repeat until you've covered all of the vertices. Since your storing and updating the path length instead of actually recalculating it each time (which would require (O(N^2)), it can be done in O(N).

This allows traversing of the cycle in O(N). However, it is not an exact algorithm. That requires checking that you shouldn't have used the first+i and/or last-j for some i,j instead. To fully check for that requires essentially O(N^2).

Although, you might be about to do it in around O(N log N) by cleverly determining where those edge cases are possible. I doubt an exact linear algorithm is possible.

Nuclearman
  • 5,029
  • 1
  • 19
  • 35
0

Pick a link on the cycle. The longest path either does or does not go through that link, so let's work out the best answer in either case and pick whichever of those is best.

If the longest path does not go through the cycle link, delete the link to produce a tree. From the leaves up work out, at each node, the longest path under that node, and the longest path from that node to any descendant. At each node you can work out the answers by looking at the answers at its children. The answer at the root gives you the longest path.

If the longest path does go through the link you picked, it must consist of a part that goes clockwise from the one end of the link and a part that goes counter-clockwise from the other end of the link. The lengths of these two add up to no more than one plus the number of links that go to make up the cycle. For i = 1 to limit work out the cost of the clock-wise and counter-clockwise paths from each side of the link and keep a running maximum. The longest path passing through the link has length the sum, for some k, of the longest path going clockwise for up to k links and the longest path going counter-clockwise for up to N-k links (with possibly some fiddling of similar cost of -ve link costs are present). So you can find the longest path that goes through your chosen link with cost also O(n).

Computing two cases each of cost O(n) and chosing the best gives you total cost O(n)

mcdowella
  • 19,301
  • 2
  • 19
  • 25
  • 1
    Did you take negative weights into account? What if, between the chosen node and the longest path, there is some edge with a gigantic negative weight? It'll find the longest path that's on the same side as the node (not the global longest path). – Bernhard Barker Jan 09 '13 at 11:22
  • When you say "You can show this by picking an arbitrary node as root and looking at the longest path, which must go through the root", do you just mean "the longest path that goes through the root"? Because the longest path in the tree overall will not necessarily go through some arbitrarily chosen root (which is after all just an arbitrarily chosen vertex). But in that case, your argument doesn't seem to explain why the longest path overall will be found -- "half-paths" seem to be w.r.t. the chosen root. The algorithm seems plausible but I don't yet understand why it must work! – j_random_hacker Jan 09 '13 at 11:47
  • @Dukeling I was wrong in the case of -ve weights for a tree. I have replaced that section with a reference to a solution for a DAG. – mcdowella Jan 09 '13 at 20:26
  • @j_random_hacker I failed to reconstruct a proof of something I was told as a fact - at least in the case of +ve weights. I was told to imagine holding up the tree by the first point chosen. At least one of the two points at either end of the longest path must hang down from there, at a distance of at least half of the longest path from it. If there is a point further from the original point than either of these two points, I think you can use it in combination with the so-called longest path to create a longer path, which is a contradiction. – mcdowella Jan 09 '13 at 20:33
  • @Dukeling - oops, a tree is not directed so I have made yet another attempt on the tree case. – mcdowella Jan 09 '13 at 21:11