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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – superuseroi
    Apr 10, 2015 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, 2015 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, 2015 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$
    – Abhijit Sarkar
    Dec 19, 2018 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, 2018 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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