A.
Now to stop the communication between the two cities, we need to find the minimum cut between these two citie, so we can use Karger’s algorithm. In this algorithm, we use the form of edge contraction which means that when you have two nodes \(u,v\) you make them one single node we can call \(w\). Then you delete any edges between \(u\) and \(v\), and then all the edges that were coming into \(u,v\) or leaving \(u,v\) become the edges for \(w\). We continue this algorithm by randomly choosing two vertices that are attached by two edges, and contracting them. We continue this until only two vertices are left. This will give us a cut for this graph. Since in this final graph our terminal nodes will never contract with each other they will be separated by only this single edge. This edge is the only cut on G but because this is random this cut may not be the minimum cut.
Runtime: We need to have \(n\) number of iterations because at each iteration we decrease the number of nodes by 1. We want to decrease it by \(n-2\), so that means we have to do it on the order of \(n\). Since any node could be connected to every single other node doing a single contraction could take worst case linear time to do all the updates.
Runtime: \(n^2\) where n is the number of vertices.
Since this is a random algorithm we only have a small probability that we get the min cut. If we repeat this algo \(\binom(n,2)*ln(n)\) times and we choose the smallest cut after all the iterations the probability that we DONT find the min cut is \(\frac{1}{n}\).
B.
Now to find the 2-time algorithm for a cut with these three cities, we will use a Karger’s algorithm again. First we find the min cut between Yunkai and the rest of the graph. Then we find the min cut between Astapor and the rest of the graph. Then find the min cut between Meereen and the rest of the graph. Then now we have three different min-cuts and all those edges separates the three cities.
Let \(opt\) be the optimal cost and let \(B_i\) be a cut that separates city \(i\) from the rest of the graph. Since each edge in the optimal solution is in 2 different components each edge must be in two of the cuts \(B_i\). So that means the sum of all of the \(B_i\)’s must be equal to two times the optimal value. We also know that due to our algorithm we found the min-cuts we can call \(C_i\) which are smaller than \(B_i\).
So the sum of all the \(C_i <=\) sum of all the \(B_i\), which is \(=2*opt\)
So our algorithm is at most 2 times worse than the optimal solution.
C.
Start off by removing all the edges that you have in your graph. Then add one edge and peform Floyd Warshall just to see which cities are now connected. If we have \(m\) or more infinities, that means at least \(m\) cities are still unconnected and we can continue to add more edges. Once the number of infinities returned by Floyd-Warshall is \(m-1\), that means we have to stop because we have not separated \(m\) cities. We try to add the max number of edges because each edge we add to the graph is an edge we do not have to guard. So keep adding edges until you get \(m-1\) infinities back.
D.
I don’t know.