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.
Let M'
be the matrix obtained by changing some values in M
and 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 vertexi
andj
, since the graph is undirected, triviallyM'[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
,M[i][j]
refers to the weight between vertexi
andj
. - Try creating a
Maximum Spanning Tree
from the values in M[i][j](I usedKruskal's Algorithm
). - 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
i
andj
, and so according to theFord Fulkerson's algorithm
this 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 valueM[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], thusM[i][j]
need to be incremented. This change will be equal to2*(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?