The inverse problem of MST (inverse-MST - minimum spanning tree inverse problem) in O (N M2)

Given a weighted undirected graph G with N vertices and M edges (without loops and multiple edges). It is known that the graph is connected. Also, given a skeleton T of the graph (ie, selected the N-1 rib, which form a tree with N vertices). Want to change the weights of the edges so that the skeleton of T is specified by the minimum spanning tree of this graph (more precisely, one of the minimum spanning tree), and to do this so that the total change of all was the smallest scales.
Solution

We reduce the problem of inverse-MST problem to min-cost-flow, more precisely, the problem of the dual min-cost-flow (in the sense of duality of linear programming problems), then solve the latter problem.

Thus, suppose that a graph G with N vertices, M edges. The weight of each edge is denoted by Ci. We assume without loss of generality that the edges with numbers from 1 to N-1 are edges T.
A. A necessary and sufficient condition for the MST

Suppose we are given a skeleton of S (not necessarily minimal).

We first introduce notation. Consider some edge j, not belonging to S. Obviously, the graph S has only one path connecting the ends of this edge, ie the only path that connects the ends of j and consisting only of edges belonging to S. We denote by P [j] the set of edges forming the path for the j-th rib.

In order to be a skeleton of S is minimal if and only if:

Ci <= Cj for all j ∉ S and every i ∈ P [j]

It may be noted that, since in our problem belongs to the edge skeleton of T 1 .. N-1, then we can write this condition as follows:

Ci <= Cj for all j = N.. M and every i ∈ P [j]
(And all the i lie in the range 1 .. N-1)

Two. Count the ways

The notion of graph paths is directly related to the previous theorem.

Suppose we are given a skeleton of S (not necessarily minimal).

Then count the ways H for a graph G is the following graph:

    * It contains M vertices, each vertex in H bijectively corresponds to some edge in G.
    * The graph H is bipartite. In the first of its share are node i, which correspond to the edges of G, belonging to the skeleton S. Accordingly, in the second part are the top j, which correspond to the edges not belonging to S.
    * An edge is drawn from vertex i to vertex j if and only if i belongs to P [j].
      In other words, for each vertex j of the second part it consists of edges from all vertices of the first part of the set of edges of P [j].

In the case of our problem, we can simplify the description of some ways to graph:

edge (i, j) exists in H, if i ∈ P [j], j = N.. M, i = 1 .. N-1

Three. The mathematical formulation of the problem

Purely formal inverse-MST problem can be written as follows:

find an array A [1 .. M] such that
Ci + Ai <= Cj + Aj for all j = N.. M and every i ∈ P [j] (i in 1 .. N-1)
and minimize the amount of | A1 | + | A2 | + ... + | Am |

Here at the desired array A, we mean those values ​​that you want to add to the weights of the edges (ie, solving the problem inverse-MST, we replace each edge weight of Ci i on the value of Ci + Ai).

Obviously, it makes no sense to increase the weight of edges belonging to T, ie

Ai <= 0, i = 1 .. N-1

and does not make sense to shorten the edges not belonging to T:

Ai> = 0, i = N.. M

(Because otherwise we will only worsen the response)

Then we can slightly simplify the problem by removing the sum of the following modules:

find an array A [1 .. M] such that
Ci + Ai <= Cj + Aj for all j = N.. M and every i ∈ P [j] (i in 1 .. N-1)
Ai <= 0, i = 1 .. N-1,
Ai> = 0, i = N.. M,
and minimize the amount of An + ... + Am - (A1 + ... + An-1)

Finally, just change "minimize" to "maximize", and in the amount of change all the signs to the contrary:

find an array A [1 .. M] such that
Ci + Ai <= Cj + Aj for all j = N.. M and every i ∈ P [j] (i in 1 .. N-1)
Ai <= 0, i = 1 .. N-1,
Ai> = 0, i = N.. M,
and maximize the amount of A1 + ... + An-1 - (An + ... + Am)
4. Reducing the problem to the inverse-MST problem, the dual problem of the assignment

Formulation of the inverse-MST, we just gave is the formulation of a linear programming problem with unknown A1 .. Am.

We apply the classical technique - consider its dual problem.

By definition, to obtain the dual problem, you need to compare each inequality, the dual variable Xij, interchange the roles of the objective function (which had to be minimized) and the coefficients on the right side, change the characters "<=" on "> =", and vice versa, change to the maximization minimization.

Thus, the dual to the inverse-MST problem:

find all Xij for each (i, j) ∈ H, such that:
all Xij> = 0,
for each i = 1 .. N-1 Σ Xij for all j: (i, j) ∈ H <= 1,
for each j = N.. M Σ Xij for all i: (i, j) ∈ H <= 1,
and to minimize Σ Xij (Cj - Ci) for all (i, j) ∈ H

The latter task is a task assignment: we need the graph to select multiple paths H edges so that none of the edges does not interfere with others in the top, and the sum of weights of edges (edge ​​weights (i, j) is defined as Cj - Ci) be the smallest .

Thus, the dual problem of inverse-MST is equivalent to the assignment. If we can solve the dual problem of the assignment, we will automatically solve the problem of inverse-MST.
Five. The solution of the dual assignment problem

First, will pay little attention to the particular case of the assignment problem, which we have received. First, it is unbalanced assignment problem, because one portion is N-1 vertices, and another - M vertices, ie in general, the number of vertices in the second one more than an order of magnitude. To solve such a dual assignment problem is a special algorithm that decides it for O (N3), but here, this algorithm will not be considered. Second, such a task assignment can be called a task assignment with weighted vertices: the edge weights are set equal to 0, the weight of each vertex of the first part is set equal to-Ci, from the second part - equal to Cj, and the solution of the resulting problem will be the same.

We will solve the problem of the dual problem of the assignment using a modified algorithm for min-cost-flow, which will be to find the minimum cost flow and simultaneously a solution of the dual problem.

Reduce the problem of appointments to the task of min-cost-flow very easily, but for the sake of completeness we describe this process.

Add to the graph source s and drain t. From s to each vertex of the first part will hold an edge with capacity 1 and cost = 0. From each vertex of the second part will hold an edge to t with capacity 1 and cost = 0. Capacities of all edges between the first and second installments are also set equal to 1.

Finally, the modified algorithm to min-cost-flow (described below) to work, you need to add an edge from s to t with capacity = N +1 and the value 0.
6. A modified algorithm for min-cost-flow solutions for the assignment problem

Here we consider the successive shortest path algorithm with potentials, which resembles the usual algorithm min-cost-flow, but also uses the concept of potential, which by the end of the algorithm will contain the solution to the dual problem.

We introduce some notation. For each edge (i, j) is denoted by Uij its capacity through Cij - the cost, through Fij - flow along this edge.

Also, we introduce the notion of potential. Each vertex has its own potential PIi. The residual value of an edge CPIij is defined as:

CPIij = Cij - PIi + PIj

At any time of the algorithm capabilities are such that the following conditions:

if Fij = 0, then CPIij> = 0
if Fij = Uij, then CPIij <= 0
CPIij = 0 otherwise

The algorithm starts with a zero flow, and we need to find some of the initial values ​​of the potentials that satisfy the above conditions. It is easy to verify that this method is one of the possible solutions:

PIj = 0 for j = N.. M
PIi = min Cij, where (i, j) ∈ H
PIs = min PIi, where i = 1 .. N-1
PIt = 0

Actually the algorithm min-cost-flow consists of several iterations. At each iteration, we find the shortest path from s to t in residual network, and the weights of the edges using the residual value of CPI. Then we increase the flow along the path found by one, and update capabilities as follows:

PIi - = Di

where Di - found the shortest distance from s to i (again, in the residual network with edge weights CPI).

Sooner or later we will find the path from s to t, which consists of a single edge (s, t). Then, after this iteration, we need to complete the work of the algorithm: indeed, unless we stop the algorithm, it will already be on the way to a non-negative value, and add them to the answer is not necessary.

By the end of the algorithm, we obtain the solution of the assignment problem (in the form of flow Fij) and the solution of the dual assignment problem (in the array PIi).

(C PIi will need to spend a little modification, from all the values ​​PIi take PIs, because its values ​​have meaning only when PIs = 0)
6. Total

So, we decided to dual task assignment, and, consequently, the problem of inverse-MST.

We estimate the asymptotic behavior of the resulting algorithm.

First, we must construct a graph paths. To do this simply for each edge j ∉ T preorder traversal of the skeleton of T we find the path P [j]. Then we construct a graph of paths in O (M) * O (N) = O (NM).

Then we find the initial values ​​of the potentials for the O (N) * O (M) = O (NM).

Then we iterate min-cost-flow, all iterations will be no more than N (as N goes from the source of the ribs, each with a bandwidth = 1) at each iteration, we are looking at ways to graph the shortest path from source to all other vertices. Since the vertices in the graph paths is M +2, and the number of edges - O (NM), then, if you implement search for the simplest version of the shortest path Dijkstra algorithm, each iteration of the min-cost-flow will perform for the O (M2), and the whole algorithm min -cost-flow will be executed in O (N M2).

The resulting asymptotic behavior of the algorithm is O (N M2).
Implementation

We sell all of the above algorithm. The only change - instead of algorithm Dijkstra algorithm is used Leviticus, which in many tests should run slightly faster.

const int INF = 1000 * 1000 * 1000;

struct rib {
int v, c, id;
};

struct rib2 {
int a, b, c;
};

int main () {

int n, m;
cin >> n >> m;
vector <vector <rib>> g (n); / / graph in adjacency list format
vector <rib2> ribs (m); / / all edges in one list
... Reading a graph ...

int nn = m +2, s = nn-2, t = nn-1;
vector <vector <int>> f (nn, vector <int> (nn));
vector <vector <int>> u (nn, vector <int> (nn));
vector <vector <int>> c (nn, vector <int> (nn));
for (int i = n-1; i <m; + + i) {
vector <int> q (n);
int h = 0, t = 0;
rib2 & cur = ribs [i];
q [t + +] = cur.a;
vector <int> rib_id (n, -1);
rib_id [cur.a] = -2;
while (h <t) {
int v = q [h + +];
for (size_t j = 0; j <g [v]. size (); + + j)
if (g [v] [j]. id> = n-1)
break;
else if (rib_id [g [v] [j]. v] == -1) {
rib_id [g [v] [j]. v] = g [v] [j]. id;
q [t + +] = g [v] [j]. v;
}
}
for (int v = cur.b, pv; v! = cur.a; v = pv) {
int r = rib_id [v];
pv = v! = ribs [r]. a? ribs [r]. a: ribs [r]. b;
u [r] [i] = n;
c [r] [i] = ribs [i]. c - ribs [r]. c;
c [i] [r] =-c [r] [i];
}
}
u [s] [t] = n +1;
for (int i = 0; i <n-1; + + i)
u [s] [i] = 1;
for (int i = n-1; i <m; + + i)
u [i] [t] = 1;

vector <int> pi (nn);
pi [s] = INF;
for (int i = 0; i <n-1; + + i) {
pi [i] = INF;
for (int j = n-1; j <m; + + j)
if (u [i] [j])
pi [i] = min (pi [i], ribs [j]. c-ribs [i]. c);
pi [s] = min (pi [s], pi [i]);
}

for (; ;) {
vector <int> id (nn);
deque <int> q;
q.push_back (s);
vector <int> d (nn, INF);
d [s] = 0;
vector <int> p (nn, -1);
while (! q.empty ()) {
int v = q.front (); q.pop_front ();
id [v] = 2;
for (int i = 0; i <nn; + + i)
if (f [v] [i] <u [v] [i]) {
int new_d = d [v] + c [v] [i] - pi [v] + pi [i];
if (new_d <d [i]) {
d [i] = new_d;
if (id [i] == 0)
q.push_back (i);
else if (id [i] == 2)
q.push_front (i);
id [i] = 1;
p [i] = v;
}
}
}
for (int i = 0; i <nn; + + i)
pi [i] - = d [i];
for (int v = t; v! = s; v = p [v]) {
int pv = p [v];
+ + F [pv] [v], - f [v] [pv];
}
if (p [t] == ​​s) break;
}

for (int i = 0; i <m; + + i)
pi [i] - = pi [s];
for (int i = 0; i <n-1; + + i)
if (f [s] [i])
ribs [i]. c + = pi [i];
for (int i = n-1; i <m; + + i)
if (f [i] [t])
ribs [i]. c + = pi [i];

... the output graph ...

}