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



finding missing edge in DAG which, when added, would create the longest cycle 
Actually your context tells us you are interested in a much simpler problem. Rather than finding the longest directed simple path in the graph, you are only interested in the longest directed simple path which ends at a specified vertex (the person who is using the app at that moment). So if you just construct a new graph which reverses the directions of the edges, and from that specified vertex do a DFS/BFS to find the longest directed simple path starting at that vertex, the endpoint of that path is the person who should be recommended as a person to 'thank'. In your search you can keep track of the k longest paths if you want to recommend multiple people for thanking


