[Solved]: Finding edges with minimal weight sum, such that every simple cycle contain at least one edge

Problem Detail: 

Given simple, udirected and connected graph with $n$ verticies. Every edge in this graph has some weight. I have to find (in polynomial time) a set of edges such that :

1.every simple cycle in graph contains at least one edge from this set
2.sum of weights of these edges is the least possible

I have derived the following algorithm to solve this problem.

First, apply DFS algorithm, starting from 1. vertex, to get all back edges. It is known that every simple cycle in this graph will contain at least one back edge, so 1. condition will be satisfied. To satisfy the 2. condition, we must apply DFS algorithm starting from 2. vertex, 3. vertex .... n. vertex, to get different sets of back edges, that all satisfy 1. condition, and choose set with the least sum of weights.

My question is will this algorithm give the right answer ? And if it won't, then why?

I have some doubdts about it, for example, is the set of back edges, given by DFS algorithm, is least possible to satisfy the condition that every simple cycle in the graph contain at least one edge from this set? For example, DFS has given me that $BE = \left\{ e_1, e_2, e_3, e_4 \right\}$ are the back edges of graph. So every simple cycyle will contain at least one edge from $BE$. But, is it possible that we can throw out, say, $e_3$ and still every simple cycle in graph will contain at least one edge from $\left\{ e_1, e_2, e_4 \right\}$ ?

Asked By : Jevgenijs Strigins

Answered By : Louis

To turn some of my hints into an answer, the problem with your solution is that the DFS phase doesn't do anything to optimize the weight of the complement of the tree. Here is a solution.

Let $G=(V,E)$ be your graph, $w : E\to \mathbb{Z}$ the weight function, which we extend linearly to $2^E$. Call the set we are looking for $B$.

Property (1) implies that $C := E\setminus B$ is acyclic. Otherwise, $C$ contains some cycle, contradicting the fact that $B\cap X\neq \emptyset$ for every cycle $X$ in $G$.

Property (2) implies that $w(C)$ should be as large as possible. Since $w(B) = w(E) - w(C)$, minimizing $w(B)$ is just maximizing $w(C)$.

So, the algorithm is just to compute the maximum weight forest in $G$, and return the complement. (The MWF isn't necessarily a spanning tree if there are negative weights.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19237