[Solved]: Proof for variation of Prim's and Kruskal's to find maximum-weight acyclic subgraph

Problem Detail: 

I have been scratching my head to find good counter examples to the following problem:

Suppose we are given a directed graph G=(V,E) in which every edge has a distinct positive edge weight. A directed graph is acyclic if it has no directed cycle. Suppose that we want to compute the maximum-weight acyclic subgraph of G (where the weight of a subgraph is the sum of its edges' weights). Assume that G is weakly connected, meaning that there is no cut with no edges crossing it in either direction.

Here is an analog of Prim's algorithm for directed graphs:
Start from an arbitrary vertex s, initialize S={s} and F=∅.
While S≠V, find the maximum-weight edge (u,v) with one endpoint in S and one endpoint in V−S. Add this edge to F, and add the appropriate endpoint to S.

Here is an analog of Kruskal's algorithm. Sort the edges from highest to lowest weight. Initialize F=∅. Scan through the edges; at each iteration, add the current edge i to F if and only if it does not create a directed cycle.

Both algorithm fail.
There should be a 4 vertices graph with 2 cycles that demonstrate this.

So far I played with different weights for this:

A<----B ^⟍    ^ |  ⟍  | |    ➘| C<--- D 

However I am not yet able to prove that both algorithms fail. I would love any suggestioin

Asked By : superuseroi

Answered By : D.W.

This is a nice exercise. You should probably do it yourself, to get the learning benefit. I suggest that you enumerate all non-isomorphic graphs with 3 vertices or 4 vertices, and for each such graph, try playing with the weights to try to find a counter-example. Basically, keep trying what you've been doing, but be more systematic and exhaustive about it. You're on the right direction -- keep at it.

Best Answer from StackOverflow

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