0
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Apr 30, 2012 at 5:15

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I guess so.. hadn't thought of it like that.. Do'h. THanks $\endgroup$
    – utunga
    May 2, 2012 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.