5
Let G = (V, E) be a flow network
with source s, sink t, and capacity function c(·). Assume that, for every
edge e ∈ E, c(e) is an integer. Define the size of an s-t cut (A, B) in G
to be the number of edges directed from A to B. Our goal is to identify,
from among all minimum cuts in G, a minimum cut whose size is as small
as possible.
Let us define a new capacity function c'(·) for G as follows. For each
edge e ∈ E, by c'(e) = m·c(e)+1. Suppose (A, B) is a minimum
cut in in G with respect to the capacity function c'(·).
(a) Show that (A, B) is a minimum cut with respect to the original capacity
function c(·).
(b) Show that, amongst all minimum cuts in G, (A, B) is a cut of smallest
size.
(c) Use the results of parts (a) and (b) to obtain a polynomial-time algorithm
to find a minimum cut of smallest size in a flow network.

How can I write a polynomial time algorithm for this? Any Idea?

Programming lover
  • 179
  • 4
  • 14
  • Well, you could look up "polynomial min cut" with google and get [here](https://en.wikipedia.org/wiki/Cut_(graph_theory)) with the first search result, and maybe follow the link to the [Edmonds-Karp algorithm](https://en.wikipedia.org/wiki/Edmonds–Karp_algorithm). – pjs Sep 15 '15 at 19:51
  • 2
    They even give you the new capacity function. VtC too broad because lazy homework question. – David Eisenstat Sep 15 '15 at 19:54
  • Possible duplicate of [Find all edges in min-cut](https://stackoverflow.com/questions/21471043/find-all-edges-in-min-cut) – grepcake Mar 28 '19 at 19:30

2 Answers2

2

I won't spoil the answer, but I will leave a hint to any student who finds this post in the future. Consider what happens if you take two min-cuts (A,B) and (C,D) in G, such that the number of edges in one is minimal and the number of edges in the other is not. Then map them to G' and consider the value of these two cuts.

Matthew Riley
  • 45
  • 1
  • 9
-2

Search up dijkstra's algorithm, it's usually used for shortest paths in a graph. I dont fully understand the algorithm you are trying to achieve but I feel it is very similar and the thinking behind dijstra's could be used

R Nar
  • 5,465
  • 1
  • 16
  • 32