finding missing edge in DAG which, when added, would create the longest cycle

Hey all,

Not sure if this is a math problem or an algorithm problem - but hoping it has a math style answer.

If I have a directed graph I can find all the closed loops - easy. (Actually not at all easy but I guess it is at least well studied). What I want to do is to find the arcs such that if one extra edge was added they would be turned into loops.

That is, you add one edge you get a loop. There are trivial solutions in the sense that for every directed edge you can simply add an edge back to the source to create a cycle, but I'm after the longer non-trivial solutions, so let's add the restriction that we want to find the edge such that when that single edge is added it creates the longest cycle.

Maybe you know of some specific area of research on this that I should read up on? Have feeling I'm gonna be digging pretty deep (as a programmer) to solve this one.

--

By way of context (not part of the problem but in case it helps) I am building a web/mobile app where people can 'thank' other people. I want to find the people 'closest to you' (in the network) so that if you have thanked someone it will recommend the person (or persons) with whom you could 'close the loop' in the sense of creating a 'cycle of thankyous'. Completely out of scope to describe why on earth I think that is a good idea, but obviously something to do with reciprocity etc..

• You need to find the longest directed simple path (no repeated vertices) in the given directed graph. If your graph is small (less than 1000 vertices) you can use a simple brute force algorithm and get an answer in less than an hour, or so I would hope. For larger graphs, there might be a chance at a quick answer if they are sparse. You might use dynamic programming to build a list of some paths greater than a certain threshold, but that can be combinatorially explosive sometimes. Gerhard "Ask Me About System Design" Paseman, 2012.04.29 Apr 30 '12 at 5:15