I was asked the following problem in an interview:
Let M be a N X N matrix, such that:
M[i][j] >= 0; 1 <= i,j <= N and i != j M[i][j] = 0; if i = j M[i][j] = M[j][i]; 1 <= i,j <= N
We are allowed to increase any of the entry in
M[i][j] by any positive number, that we can increase the value of any cell in
M[i][j] as much as we want.
M' be the matrix obtained by changing some values in
x be the sum of all the changes made in M.
The task is to obtain M' such that it represents a graph with N vertex and satisfies following two conditions:-
M'[i][j]= max flow between vertex
j, since the graph is undirected, trivially
M'[i][j] = M'[j][i].
- x is minimized, that is sum of all the changes made in M to get M' is minimum.
consider for example,
M = 0 7 11 6 7 0 9 8 11 9 0 4 6 8 4 0 M'= 0 9 11 8 9 0 9 8 11 9 0 8 8 8 8 0 x = 16.
Here is how I approached the problem.
- Assume that in
M[i][j]refers to the weight between vertex
- Try creating a
Maximum Spanning Treefrom the values in M[i][j](I used
- Now, while adding an edge between some pair i and j in the Maximum ST, one of the two conditions may arise- either no path exists between i and j, in this case simply add this edge between them, since we have been adding edges in a non-increasing order(as we are creating a Maximum Spanning Tree) this will be a 'bottleneck-edge' in the path between
j, and so according to the
Ford Fulkerson's algorithmthis is also the max flow between i and j, so no changes required to be made(
i.e. nothing to increase here as the max-flow is equal to the initial value
M[i][j]). The other case is when there already exists a path between i and j, and since we are adding edges in non-increasing fashion, the current flow between i and j will be greater than the value M[i][j], thus
M[i][j]need to be incremented. This change will be equal to
2*(current_flow_between_i_and_j - M[i][j])(as both M[i][j] and M[j][i] need to be changed and by equal amount).
And my approach was actually giving correct answer to the example test cases given by the interviewer, but to my surprise the interviewer told me that my approach was wrong and won't always work. I even tried my approach on test cases made by myself, and it seems to work correctly(or atleast this what I think). Where am I wrong in my approach and what can be a correct solution?