PROBLEM LINK:
Author: Misha Chorniy
Tester: Ajay K. Verma
Editorialist: Ajay K. Verma
DIFFICULTY:
Hard
PREREQUISITES:
Max-flow min-cut theorem, Dijkstra algorithm
PROBLEM:
Given a weighted directed graph G, two nodes s, t in the graph and an integer k, compute the capacity of the k-th min-cut between s and t.
QUICK EXPLANATION:
Create an enumeration tree for all cuts between s and t such that each cut in the enumeration tree appears exactly once. Moreover, if two cuts satisfy parent-child relationship in the enumeration tree, then the capacity of the parent cut should be lower or equal than the capacity of the child cut. We can run Dijkstraās Algorithm on this tree to get the K smallest capacity cuts.
EXPLANATION:
We are given a weighted directed graph G, two nodes s, t in the graph and an integer k. The task is to compute the capacity of the k-th min-cut between s and t.
We create an enumeration tree to iterate through all s-t cuts. Since the number of s-t cuts is exponential in the size of the graph, we create this enumeration tree lazily.
The root node of the enumeration tree corresponds to the min-cut. From a node, we create extra restrictions and for each restriction create a branch in the enumeration tree, such that all the cuts in that branch satisfy these restrictions. The restrictions are chosen in such a way that each cut belongs to exactly one branch. Also the enumeration tree satisfies the property that a cut corresponding to the parent node has capacity lower or equal to the capacity of the cut corresponding to a child node.
If we can construct this enumeration tree lazily, then we only need to run Dijkstraās algorithm from the root, and terminate the Dijkstraās algorithm after K iterations. The cut corresponding to the last iteration would be the K-th min cut.
Next, we show how to construct such an enumeration tree.
The root of this tree corresponds to the min s-t cut. Now consider a node, which corresponds to a cut having edges {e1, e2, ā¦, ek}. We create (1 + k) restriction sets, which are as follows:
- e1
- e1ā e2
- e1āe2ā e3
ā¦
k) e1āe2āā¦ek - 1ā ek
k + 1) e1āe2āā¦ekā
The first restriction says that only those restrictions should be considered, which use edge e1, the second restriction says that only those cuts should be considered which do not contain e1, but contain e2, and so on.
It is easy to see that these restrictions ensure that any cut can satisfy at most one of the restriction set, moreover, each cut must satisfy one of the restrictions as the union of all restrictions cover all cuts.
In the enumeration tree, all cuts in a subtree satisfy restrictions imposed by branches on the path from the root of the current subtree to the root of the enumeration tree. The root node of a subtree can be any cut satisfying all restrictions. However, we pick it to be the min-cut satisfying all restrictions. This ensures that the root of a subtree is the smallest capacity cut in the subtree.
Now, we know the existence of the enumeration tree, however we still need to find a way to construct it lazily. Based on our approach, in order to construct the enumeration tree, the only thing that we need to compute is the min cut satisfying a set of restrictions, where each restriction is about inclusion or exclusion in the cut.
If there were no restrictions, then a min-cut can be computed easily by running the max flow algorithm based on max-flow min-cut theorem.
Note that edge exclusion constraint is easy to handle. Supposed we want a cut which should not contain the edge e, then we should modify the graph by removing this edge, and then compute the min-cut. Alternatively, we can make the weight of this edge to be infinity. That way this edge will never be selected in the min-cut.
The edge inclusion constraint can also be handled in a similar way. Suppose we have a constraint that the cut must contain the edge e = (u, v). Then we modify the graph by creating two edges (s, u) and (v, t) both of weight infinity, and then compute the min-cut of the modified graph. If the min-cut does not contain the edge e, then either both u and v be in the partition containing s, or both u and v in the partition containing t. In the first case edge (v, t) with cross the cut, i.e., the cut capacity would be infinity, while in the second case edge (s, u) will cross the cut resulting in an infinite capacity cut. Hence, if there is a cut satisfying the inclusion constraint, the addition of the two edges (s, u) and (v, t) will enforce that a min-cut satisfying the inclusion constraint is generated.
In order to find the K-th min cut, we use a simple variation of Dijkstraās algorithm, in which a nodeās weight is the capacity of the cut it corresponds. Each node in the enumeration tree may have up to M branches, where M is the number of edges in the graph, Hence, we may need to run the max-flow algorithm at most O (MK) times.
TIME COMPLEXITY:
O (MK * Tmax_flow)
AUTHORāS AND TESTERāS SOLUTIONS:
Authorās solution can be found here
Testerās solution can be found [here][444]