Welcome to MathOverflow

Question

0

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

flag	asked Apr 30 2012 at 4:37 utunga 53●3

1

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 – Gerhard Paseman Apr 30 2012 at 5:15

David Benson-Putnins · Accepted Answer · 2012-04-30 07:47:41Z UTC

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

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.