2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ so I had a good go at this and in what I was able to demonstrate is that both algorithms fail at one main point: they stop when they have a tree, yet they do not continue to add edges although they do not create a cycle. Is this your conclusion too? is there anything else to be seen? $\endgroup$ – superuseroi Apr 10 '15 at 16:30
  • $\begingroup$ @superuseroi, Hmm, that doesn't sound entirely right. I believe you are right that the Prim's-variant will always stop with a tree, but that's not correct of the Kruskal's-variant: the Kruskal's-variant can output a non-tree in some cases (consider running it on a DAG, for instance). By the way, all it takes is one counterexample to prove that the algorithm doesn't work, so you don't have to characterize all failure cases to prove that both algorithms don't work. $\endgroup$ – D.W. Apr 10 '15 at 16:44
  • $\begingroup$ @WD thank you so much for your response. As far as I can see because Kruskal's algo uses a disjoint set (unionfind) and will stop when there is 1 single set (meaning every set was U with every other) this happens only when we have collected V-1 edges. There can be a graph where there is a max acyclic subgraph which has more than V-1 edges. As for running it on a DAG I see that the tree could be weakly connected that's all. What do you see? thank you! $\endgroup$ – superuseroi Apr 11 '15 at 11:37
  • $\begingroup$ Take another look at the definition of the "analog of Kruskal's algorithm". Note that it is not specified to use union-find. Also note that the real Kruskal's algorithm can be implemented using union-find, but the variant doesn't seem like it can. Anyway, CS.SE isn't a discussion forum and isn't a good place if you want a series of follow-up questions answered, so I'm going to sign off here -- this site is best for posting a single question and getting an answer to it (if you have other questions they should be posted separately). $\endgroup$ – D.W. Apr 11 '15 at 16:30
  • $\begingroup$ Yes perfect I understand, thank you for your input it was great! $\endgroup$ – superuseroi Apr 11 '15 at 17:53

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.