# Homework Help: Finding cycles in a graph

Tags:
1. Feb 15, 2016

### wololo

1. The problem statement, all variables and given/known data

2. Relevant equations
Recursion, graphs, DFS
3. 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

2. Feb 15, 2016

### wololo

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

3. Feb 16, 2016

### wololo

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