Min weight feedback edge set with DFS?

Question

Exercise from The Algorithm Design Manual

6-10. [4] Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F.

(b) Suppose that G is a weighted undirected graph with positive edge weights. Design an efficient algorithm to find a minimum-weight feedback-edge set.

My proposed solution for (b) is to run DFS with getting max weight as the tie breaker. Then every back edge will always be the lowest weighted edge in its cycle. I'm wondering if this is a valid solution.

Answer 1

Here is how I would tackle this problem.

For simplicity, let's just assume that G is connected (The algorithm to be described below can be easily extended for the case when G is not connected).

First, for any feedback-edge set F, it must be true that the graph G' = (V, E-F) doesn't have any cycle. This follows directly from the definition of feedback-edge sets.

Since we are looking for the set F that has minimum total weight, G' should be a tree and the edges in G' must have the maximum total weight possible (why ?)
→ G' must be a maximum spanning tree.

So now the original problem is reduced to finding a maximum spanning tree. You may already know that the Kruskal's algorithm can be used for finding a minimum spanning tree. With a little modification, you can use Kruskal's algorithm to find a maximum spanning tree. https://stackoverflow.com/questions/4992664/how-to-find-maximum-spanning-tree

So in conclusion, the algorithm I just described has running time of O(E log V) time (which is just the running time of Kruskal's algorithm)

Answer 2

Actually, no, a counter example:

A --10-- B -- 10 -- C
          \        /
           6     4
            \   /
              D

DFS will go like this:

A -> B -> C -> D

And the min feedback edge of that graph will become a tree edge.