Question

Let G = (V, E, W) be a connected weighted graph where each edge e has an associated non-negative weight w(e). We call a subset of edges F subset of E unseparating if the graph G' = (V, E\F) is connected. This means that if you remove all of the edges F from the original edge set, this new graph is still connected. For a set of edges E' subset of E the weight of the set is just the sum of the weights of the individual edges that is w(E') = sigma_e element of E' w(e). Give a polynomial time algorithm to find the unseparating set with maximum weight.

Answer 1

An undirected graph is acyclic (i.e., a forest) iff a DFS yields no back edges. Since back edges are those edges (u, v) connecting a vertex u to an ancestor v in a depth-first tree, so no back edges means there are only tree edges, so there is no cycle. So we can simply fun DFS. If find a back edge, there is a cycle. The complexity is O(V ) instead of O(E + V ). Since if there is a back edge, it must be found before seeing |V | distinct edges. This is because in a acyclic (undirected ) forest, |E| ≤ |V | + 1