title: Longest path in a particular type of graph
body: <p>I know that the <a href="http://en.wikipedia.org/wiki/Longest_path_problem" rel="nofollow noreferrer">longest path problem</a> 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:</p>
  
  <p><img src="https://i.stack.imgur.com/D44sh.png" alt="graph"></p>
  
  <p>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. </p>
  
  <p>The algorithm should be linear in the size of the cycle. But any ideas are appreciated.</p>