Problem:
The minimum s-t cut problem is the following. The input is an undirected graph, and two distinct vertices of the graph are labelled "s" and "t". The goal is to compute the minimum cut (i.e., fewest number of crossing edges) that satisfies the property that s and t are on different sides of the cut.
Suppose someone gives you a subroutine for this s-t minimum cut problem via an API. Your job is to solve the original minimum cut problem (the one discussed in the lectures), when all you can do is invoke the given min s-t cut subroutine. (That is, the goal is to reduce the min cut problem to the min s-t cut problem.)
Now suppose you are given an instance of the minimum cut problem -- that is, you are given an undirected graph (with no specially labelled vertices) and need to compute the minimum cut. What is the minimum number of times that you need to call the given min s-t cut subroutine to guarantee that you'll find a min cut of the given graph?
Solution:
Wow - that's a mouthful, but the solution is simple. Fix $ s $ to be one of the vertex and $ t $ varies across all others, then we are done by picking the smallest one, therefore we need at most $ n - 1 $ call.
If I add two vertices $ s $ and $ t $ connected to every other nodes, then wouldn't I find the right min cut with just one call, the answer is no because that min cut will necessary be of size $ n $, and after removing the added edges the 'min' cut might not be minimal.
The minimum s-t cut problem is the following. The input is an undirected graph, and two distinct vertices of the graph are labelled "s" and "t". The goal is to compute the minimum cut (i.e., fewest number of crossing edges) that satisfies the property that s and t are on different sides of the cut.
Suppose someone gives you a subroutine for this s-t minimum cut problem via an API. Your job is to solve the original minimum cut problem (the one discussed in the lectures), when all you can do is invoke the given min s-t cut subroutine. (That is, the goal is to reduce the min cut problem to the min s-t cut problem.)
Now suppose you are given an instance of the minimum cut problem -- that is, you are given an undirected graph (with no specially labelled vertices) and need to compute the minimum cut. What is the minimum number of times that you need to call the given min s-t cut subroutine to guarantee that you'll find a min cut of the given graph?
Solution:
Wow - that's a mouthful, but the solution is simple. Fix $ s $ to be one of the vertex and $ t $ varies across all others, then we are done by picking the smallest one, therefore we need at most $ n - 1 $ call.
If I add two vertices $ s $ and $ t $ connected to every other nodes, then wouldn't I find the right min cut with just one call, the answer is no because that min cut will necessary be of size $ n $, and after removing the added edges the 'min' cut might not be minimal.
No comments:
Post a Comment