Longest path in a particular type of graph

Question

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:

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.

Answer 1

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.

->

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.