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..