STMINCUT - Editorial

PROBLEM LINK:

Practice

Contest

Author: Trung Nguyen

Tester: Suchan Park

Editorialist: Suchan Park

DIFFICULTY:

Medium-Hard

PREREQUISITES:

How to construct minimum spanning trees + Very advantageous if you know what Gomory-Hu Tree is.

PROBLEM:

We want to increase some elements of a given matrix A so that there exists a graph G such that for all 1 \le i, j \le n, A_{i, j} equals to the i-j min-cut cost of G. What is the minimum possible total amount of increases?

QUICK EXPLANATION:

We can reduce the problem from graph to tree, from the theory of Gomory-Hu tree. After that, we can prove that the optimal graph for the given matrix is the maximum spanning tree.

EXPLANATION:

First, we have to think how to check whether there exists a graph G, such that for all 1 \le i, j \le n, the i-j min-cut cost of G equals to A_{i, j}. Let’s call this state as valid.

The easiest way one could think is to generate every possible graph G (although there are infinite amount of them), make a matrix B such that B_{s,t} equals to the s-t min-cust cost, and check whether A = B. Then, how to compute the matrix B? By some prior knowledge or googling, one can find Gomory-Hu Tree can solve the exact same problem.

What is a Gomory-Hu tree? Given a graph G, the algorithm produces a tree T that has the exact same min-cut cost for every possible pair of vertices s and t. Also, for every possible tree T, we can find a graph G such that when we give G as an input, the algorithm produces T – it is T itself.

This means, A is a valid matrix if and only if there exists a tree T, such that for all 1 \le i, j \le n, the i-j min-cut cost of T equals to A_{i, j}.

Usually, trees can be easily dealt than general graphs. Given a tree T, let’s try to compute the s-t min-cut cost. From the definition, we need to see all paths from s to t. But since T is a tree, the path between them is guaranteed to be unique. Therefore, s-t min-cut cost of the tree equals to the minimum weight over all edges on the path from s to t. (if we cut that edge, the path is disconnected)

Now, from this knowledge, let’s find an algorithm that checks whether A is a valid matrix. It is hard to think of it easily, so I drew an example tree and its min-cut cost matrix.

As you can see, there are lots of 1s in this matrix. Why? Since 1 is the minimum edge weight among all edges, so all pair of vertices whose paths pass A-H has min-cut cost 1.

On the other hand, there are only two 6s in this matrix, because 6 is the maximum edge weight among all edges, so no pair except (H, I) contains an edge whose weight is shorter than 6.

This gives a good insight. In both cases, we can find what edge is valid by looking at the shape of colored cells of the matrix, but it obviously seems easier to consider the edge with maximum weight.

Then, what if there are multiple maximum-weight edges? If you think for a while, you can notice that even in that case, 6s doesn’t appear too much.

Take a look at A-D, D-F and F-A. The matrix cells corresponding to those pairs are all 6, so how could we determine the tree? But… if you think more, you will notice that it is totally irrelevant, since nothing changes if we change the edges of the tree like:

This is because the set of path weights is guaranteed to be the same. So, from this example, we found out that any edge from that matrix that has maximum weight is guaranteed to be included, as long as it doesn’t make a cycle.

In conclusion, the algorithm which checks whether A is a valid matrix (and additionally generate a corresponding tree T) is:

  • Consider the entries in the matrix in non-ascending order. Initially the T has no edges.
  • Suppose we are considering edge u-v right now.
    • If u and v are not connected in T, u-v is guaranteed to be inside T, so add u-v into T.
    • Otherwise, nothing happens.

You can see the algorithm is surprisingly similar to Kruskal’s algorithm. And actually it is true, this algorithm just computes the maximum spanning tree of the graph made by the graph from A (A is the adjacency matrix) Therefore, the time required is O(N^2 \log N) (Kruskal’s) or O(N^2)(Prim’s).

Now, let’s go through our original problem. When do we want to increase the cost of edges? Clearly, if it is necessary. When is it necessary? Only if the min-cut cost is already decided and is larger than u-v. How do we know if the min-cut cost is already decided or not? Let’s see.

From the algorithm above, it is tempting to think about the maximum entry A_{u, v}, where A is the input. Do we have to increase A_{u, v}? Clearly not. This is because, since this has the maximum weight, u-v is guaranteed to be included in the optimal tree. (since it is nonsense to increase all the other edges to make u-v non-maximum) So, the edge is included in the solution tree, which means min-cut cost between u and v is fixed to A_{u, v}.

By repeating this argument, now we know when the min-cut cost is already decided – if and only if there is a path between u and v in the current tree. (exactly, forest) In that case, we can increase the edge cost by (min-cut cost of u and v) - A_{u, v}. And we know when the min-cut cost is undecided – if and only if there isn’t a path between u and v in the current tree.

In which order should we consider the entries – clear, in non-ascending order of entries! So, here, we are also computing the maximum spanning tree.

In conclusion: the maximum spanning tree of the given adjacency matrix is the optimal solution graph for this problem. After generating the tree, we can compute pairwise min-cut cost easily (for example, using DFS). Print out the difference between the sum of two matrices (input, and min-cut cost matrix of the optimal solution)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.

4 Likes

The link for Practice/Contest is redirecting to CHSIGN.

I corrected it. Thanks for pointing out. :slight_smile:

1 Like

In fact, obvious constraint A[i][k] >= min(A[i][j], A[j][k]) is sufficient.
Many O(n^3) solutions use this observation passed.

1 Like

“By repeating this argument, now we know when the min-cut cost is already decided – if and only if there is a path between u and v in the current tree.”

Shouldn’t it be “edge b/w u and v” in place of “path b/w u and v” ? Since, there is a unique path in this tree for every pair of vertices therefore, above statement will be true for every pair.

Here is how I approached it. I first made the tree T in O(N^2 log(N)). Then for each pair (u,v) if T contains edge u-v, then A[u][v] won’t change otherwise I traverse the path b/w u and v and ensure that the cost of every edge on this path is at least A[u][v], ie. increase the cost of edge if it is less than A[u][v] or increase A[u][v] if cost of all the edges is greater than A[u][v].

Solution passed but complexity is O(n^3) due to computing min-cost for each pair. Could someone please explain how can we compute pairwise min-cut cost easily(like using DFS) after constructing the tree?

No, the path is correct. The “current tree” in that sentence actually means the “current forest”, and we need to check whether those two vertices are in the same component.

Computing the pairwise min-cut cost is easy. For each node u, consider u as a root and do a DFS or BFS of the tree. Since the path of any two vertices is unique, we know the min-cut cost easily.

Thanks! I got the first part. But in the second part, for computing the pairwise min-cut cost we’ll be doing BFS(or DFS) every time u and v are in the same component. Each BFS will take O(n) time and we’ll have to do BFS for ((n^2)/2 - n + 1) pairs( since, only (n-1) pairs will lie in different components). This will again lead to O(n^3) complexity. Or am I missing some optimisation for each BFS call?

Note that if we start BFS-ing from vertex u, after the BFS is finished we visit all nodes in the tree, which means we know the min-cut cost from u to all the other vertices. Therefore only O(n) BFSs are required

After reading BlanCode’s unofficial editorial for this problem, which seems to have been taken down meanwhile, I wrote up a formal proof of how and why the solution laid out there works, to try and fill in the gaps in BlanCode’s very lucid explanation and make it clear to myself. In case anyone is interested: PDF