3
$\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$
0
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$
9
  • $\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$ 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
  • 1
    $\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
  • 1
    $\begingroup$ How's "this is a nice exercise. You should probably do it yourself" an answer to OP's question? It's a comment at best. $\endgroup$ Dec 19 '18 at 9:22
  • 1
    $\begingroup$ @AbhijitSarkar, I'm sympathetic to your viewpoint. I'm not sure whether this should count as an answer, either. $\endgroup$
    – D.W.
    Dec 19 '18 at 23:44

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.