1
$\begingroup$

Let $G = (V, E)$ be a directed weighted graph such that all the weights on the edges are positive.

In $G$, we have two nodes, $v$ and $u$, that have a path from $v$ to $u$.

The question asks to find a set of edges $ E' \subseteq E $ with the minimum weight such that $G' = (V, E') $ has no path from $v$ to $u$.

I tried the following:

We will run Dijkstra's algorithm $|E|$ times, and in each iteration, we will remove the edge with the minimum weight on the path from $v$ to $u$.

The time complexity of the method is:

$$\sum_{i=1}^{|E|} O(i \cdot \log |V|) = O(\log |V| \cdot \sum_{i=1}^{|E|} i) \underbrace{=}_{\text{complete graph}} O(|V|^4 \cdot \log |V|)$$

I wanted to ask:

  1. Is this method correct?
  2. Is there any better solution?

I got answered that this solution in wrong with a counter example.

I tried to convert this problem to a flow network problem like suggested.

Suppose that $G$ is the following graph:

enter image description here

$G$ is a valid flow network graph.

The node $s$ is the source and $t$ is the sink.

At the end of $EK$ we will get the following flow:

enter image description here

And the residual graph $G'$ look like:

enter image description here

The nodes that are in blue and orange represent the minimum cut.

Following the Max-flow min-cut theorem, we get that the maximum flow is 9.

One way to disconnect $s$ and $t$ will be by removing the following edges:

enter image description here

These are all the edges that crossing the minimum cut.

Another way:

enter image description here

Here is what I don't understand and don't know how to prove:

  1. I think that this example loses generality. I assume that $s$ has no edges entering it, and $t$ has no edges going from it. I think this is too big of an assumption.

  2. The weight of the set of edges $E'$ in my example was 9, which I think is indeed the minimum weight of the edges that will disconnect $s$ and $t$. This is also the maximum flow of the network. Is this a coincidence?

  3. I noticed that in

enter image description here

You can do the following :

a. Run a BFS scan from $s$ on $G$.

b. If you use an edge that flows it's maximum capacity, mark the edge and don't continue to the node at it end.

It will give the set of edges in the last picture.

I don't how to explain why it disconnects $s$ from $t$ in the particular graph $G$, and why this method will disconnect $s$ and $t$ in general.

$\endgroup$
1
  • $\begingroup$ Let $E' = \emptyset$. I imagine they ask something else, though, in which case, check out Max flow–Min cut. $\endgroup$
    – Pål GD
    Feb 12 at 20:35

1 Answer 1

2
$\begingroup$

The algorithm is not correct. Imagine the following graph:


   2     1     2
v --- o --- o --- u
      |     |
     2|     |2
      |  1  |
      o --- o
      |     |
     2|     |2
      |  1  |
      o --- o
      |     |
     2|     |2
      |  1  |
      o --- o

Your algorithm will output all the edges labelled 1 instead of a single edge labelled 2.

The problem you want to solve is called the Minimum Cut problem, which is solved by the Maximum Flow algorithm. Its running time is also ever-so-slightly better then your $n^4 \log n$ algorithm, but not extremely much, with Edmonds-Karp running in time $O(mn)$, i.e., $O(n^3)$.

$\endgroup$
6
  • $\begingroup$ Hello @Pål GD thank you for the answer ! I tried to convert this problem to a network flow problem like you suggested, but I didn't go far. I edited the post and wrote it there. I also wanted to ask if you can explain how you came up with the counter example. It is indeed correct and very beautiful. I'm asking this because I hope to deepen my sight on Dijkstra's algorithm in particular, and in problem solving in general. $\endgroup$
    – Daniel
    Feb 13 at 9:13
  • $\begingroup$ I have worked with cut-problems for more than 10 years. This exact graph structure has been a counter-example for many algorithmic ideas. You can start by reading an algorithms book and solve all the problems (several times). Here is a good book which is free: Algorithms by Jeff Erickson. $\endgroup$
    – Pål GD
    Feb 13 at 9:48
  • $\begingroup$ Thank you! I saw what the author wrote about solutions, but still, how I will able to determine if what I wrote is correct? In the question I posted, I was convinced that my solution is right, but you prove me wrong. Do know a valued place from where I can get solutions for the question in the book ? $\endgroup$
    – Daniel
    Feb 13 at 17:20
  • $\begingroup$ @Daniel I too have been convinced that an algorithm I came up with was correct only to find the opposite was the case; I've also been convinced an algorithm was incorrect, only to discover that it indeed is correct. $\endgroup$
    – Pål GD
    Feb 13 at 19:23
  • $\begingroup$ ... the only thing that matters is to prove that the algorithm is correct. The book should help you started in this business. Until you have a proof of correctness, you should assume the algorithm doesn't work. $\endgroup$
    – Pål GD
    Feb 13 at 19:24

Your Answer

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

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