Efficiently Finding Cycles in a Graph: A Scientific Exploration

[wololo]

Homework Statement

Homework Equations

Recursion, graphs, DFS

The Attempt at a Solution

To try to solve this algorithm, I first need to find all the basic cycles in the Graph G. When I have these cycles, I can simply pick the smallest edge in each of them and add them to the set F, while removing duplicates, which is trivial. However, I can't figure out an algorithm that would give me all the cycles in polynomial time.

I tried using a modified Depth First Search recursive method that, when it reaches a node that has already been visited, backtracks until it reaches again to find the cycle. However, for a simple graph with 8 nodes and 14 links my method gets called more than 500 times... I tried using what is described here: http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph/549312#549312

Am I thinking about this problem correctly? What approach other than finding the cycles could I use? Thanks

 

[wololo]

Could I simply use Boruvka's algorithm to get a minimum spanning tree and add these edges to F?

 

[wololo]

I think all the edges that are not in a maximum spanning tree wil give me the minimum hitting set.