title: Optimizations for longest path problem in cyclic graph
body: <p>What optimizations exist for trying to find the longest path in a cyclic graph?</p>
  <p>Longest path in cyclic graphs is known to be NP-complete. What optimizations or heuristics can make finding the longest path faster than DFSing the entire graph? Are there any probabilistic approaches?</p>
  <p>I have a graph with specific qualities, but I'm looking for an answer to this in the general case. Linking to papers would be fantastic. Here is a partial answer:</p>
  <ol>
  <li><p>Confirm it is cyclic. Longest path in acyclic graphs is easily computed using dynamic programming.</p>
  </li>
  <li><p>Find out if the graph is planar (which algorithm is best?). If it is, you might see if it is a block graph, ptolemaic graph, or cacti graph and apply the methods found in <a href="http://www.springerlink.com/content/x4fbqn45f6u1jeyh/" rel="nofollow noreferrer">this paper</a>.</p>
  </li>
  <li><p>Find out how many simple cycles there are using <a href="https://web.archive.org/web/20130906073546/http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf" rel="nofollow noreferrer">Donald B Johnson's algorithm</a> (<a href="http://normalisiert.de/code/java/elementaryCycles.zip" rel="nofollow noreferrer">Java implementation</a>). You can change any cyclic graph into an acyclic one by removing an edge in a simple cycle. You can then run the dynamic programming solution found on <a href="https://en.wikipedia.org/wiki/Longest_path_problem" rel="nofollow noreferrer">the Wikipedia page</a>. For completeness, you would have to do this N times for each cycle, where N is the length of the cycle. Thus, for an entire graph, the number of times you have to run the DP solution is equal to the product of the lengths of all cycles.</p>
  </li>
  <li><p>If you have to DFS the entire graph, you can prune some paths by computing the &quot;reachability&quot; of each node in advance. This reachability, which is mainly applicable to directed graphs, is the number of nodes each node can reach without repetitions. It is the maximum the longest path from that node could possibly be. With this information, if your current path plus the reachability of the child node is less than the longest you've already found, there is no point in taking that branch as it is impossible that you would find a longer path.</p>
  </li>
  </ol>