Finding all cycles in a graph efficiently using DFS

2 replies · 2K views · last reply
wololo
Messages
27
Reaction score
0

Homework Statement


Printed problem 6, Cycle Hitting Sets, worth 10 marks: find a polynomial time algorithm for a minimum cost hitting set of cycles in a connected undirected graph with distinct nonnegative edge costs.


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
 
Could I simply use Boruvka's algorithm to get a minimum spanning tree and add these edges to F?
 
I think all the edges that are not in a maximum spanning tree wil give me the minimum hitting set.