CHEFKC - Editorial

[djdolls]

PROBLEM LINK:

Practice
Contest

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 {e₁, e₂, …, e_k}. We create (1 + k) restriction sets, which are as follows:

1. e₁
2. e₁’ e₂
3. e₁‘e₂’ e₃
   …
   k) e₁‘e₂’…e_{k - 1}’ e_k
   k + 1) e₁‘e₂’…e_k’

The first restriction says that only those restrictions should be considered, which use edge e₁, the second restriction says that only those cuts should be considered which do not contain e₁, but contain e₂, 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 * T_{max_flow})

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here
Tester’s solution can be found [here][444]

[ceilks]

I’m afraid that distinguishing cuts by the set of included edges doesn’t work in general. In the problem description a cut is defined by a subset of the vertices, not by a subset of the edges. There are many cases where this yields different results, for example:

• Isolated vertices induce two cuts with same weight - if considering edges they do not.
• If there are two edges in between two vertices (in opposite directions) only both or none can be cut - when cosiderig edges a single edge can be cut.

The secnod problem might not show up by the way the graphs for the children nodes are constructed, but I’m not sure that point 1 is the only remaining problem.

Additionally using vertices constraints for the enumeration reduces the time complexity to O(nkT_maxflow).

Update: The algorithm in the editorial also seems to produce wrong results for connected graphs. Take s=1, t=3 and two edges e_1=(1,3) and e_2=(2,3). The algorithm in the editorial doesn’t seem to be able to find a cut through e_2. After computing the min cut \{e_1\} we arrive at the partition

1. e_1
2. e_1'

the min cut of the first is the original min-cut, the second one doesn’t contain any cut.

[anudeep2011]

I read the editorial misinterpreting edges enumeration as nodes enumeration [Thanks @ceilks, for pointing it out]

How does this work for following?

n = 5, m = 1, 1 5 is the only edge.

In this case we have 3 isolated nodes and the told algorithm can at most generate 3 answers - minimum cut + 2 (k = 1). But as per the contest problem, 2^3 = 8 possible solutions.

[wodahs_cc]

Can anyone tell me which algo to use for max_flow min_cut? I couldn’t find anything better than O(VE) which I guess will TLE in this use case?

PS: Sorry for posting as an answer but I do not have the option to comment.

[anudeep2011]

Well explained! Thanks.
Only thing missing is about how the enumerations satisfy “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”, ie, how “e1” <= “e1 e2-dash”.
Though it looks clear if though enough, might be worth mentioning it explicitly!

[adijimmy]

@djdolls @anudeep2011 can you elucidate it more. I couldn’t get the idea well.

[ceilks]

Exactly, thats where they differ. In fact the algorithm proposed in the editorial will only produce a single cut (assuming s=1 and t=5), since there is no valid cut without the single edge (because otherwise s and t would be in the same component).