I got the following task: Given a graph G := (V, E) with arbitrarily many cycles. What is the minimal set of edges so that for every cycle in the graph at least one edge is included in the set - or to be more precise, what is the sum of the weight of those edges.
My approach was pretty straight forward: I computed a maximum spanning forest over the graph, excluded each edge and proclaimed the remaing edges as result. The idea goes as follows: Since each spanning tree has no cycles I will never remove an entire cycle and thus there will not be any cycles I did not cover. Furthermore I also would not be able to remove any other edge in the graph G since if I did I would remove a cycle and thus the result would not cover all cycles. Thus I concluded my method would be correct.
However it seems that this is not the case. Can anybody enligthen me where I went wrong? I could not come up with an example that disproves my method.
This can be solved as a set covering problem.
Index the arcs 1...m. Let j refer to arbitrary arc.
Index the cycles 1...n. Let i refer to arbitrary cycle.
Have an indicator variable a_{ji} = 1 if the jth arc is part of ith cycle. 0 otherwise.
Let x_j = 1 if jth arc is selected as part of your solution.
You want to minimize the number of arcs you select.
So, minimize \sum_{j=1}^{m} x_j
The constraint is that your selected arcs should cover all cycles.
In particular, for any cycle i, you want atleast one of its edges selected.
So, model this as follows.
For each i, \sum_{j=1}^{m} a_{ji}x_{j} >= 1.
There will be n such constraints, one for each i.
The other constraint is that each x_{j} is either 0 or 1.
If you are looking to solve the weighted version, then given arc j has weight c_j, the objective needs to be changed to
\sum_{j=1}^{m} c_j x_j