3
$\begingroup$

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\}$ ?

$\endgroup$
  • $\begingroup$ I am not sure this works. Here is a hint. Think about the complement of a maximum weight forest. $\endgroup$ – Louis Dec 24 '13 at 13:48
  • $\begingroup$ By definition forest is an undirected graph, all of whose connected components are trees. Beacause graph is connected, it has only one connected component, so I assume that you meant a complement of maximum weight spanning tree of graph? $\endgroup$ – Jevgenijs Strigins Dec 24 '13 at 14:41
  • $\begingroup$ I really meant it. Imagine all the weights are -1. $\endgroup$ – Louis Dec 24 '13 at 14:57
  • $\begingroup$ So my first thaught on your hint is to find maximum weight spanning tree of graph, then, all the other edges not in this tree will have the least weight sum ? $\endgroup$ – Jevgenijs Strigins Dec 24 '13 at 15:02
1
$\begingroup$

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.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.