ways to construct a weight function which ensures nonzero circulations for any small set of cycles simultaneously, see for example. 12

Lemma 3. 1. Let C be any set of s cycles in graph G(V, E) and let E = {e1, e2, . . ., em}. For j ∈ , we define weights Then there exists a j ≤ ms such that

Note that the above lemma actually gives a list of weight functions such that for any desired set of cycles, at least one of the weight functions in the list works. Also observe that the weight of any edge under any of these functions is bounded by ms. That is, the weights are polynomially bounded as long as the number of cycles is.

The isolating weight assignment is now constructed in rounds. The strategy is to keep eliminating a small number (poly or quasi-poly) of cycles in each round by giving them nonzero circulations. This is repeated until we are left with no cycles. In every round, we add the new weight function to the current weight function on a smaller scale. This is to ensure that the new weights do not interfere significantly with the circulations of cycles which have been already eliminated in earlier rounds.

In more detail, if wi is the current weight function in the ith round, then in the next round, we will consider the weight function wi+ 1 = Nwi + w′, for some weight function w′ and a large enough number N. The number N is chosen to be larger than n ⋅ maxe w′(e), which ensures that Nwi gets precedence over w′. The weight function w′ is designed to ensure nonzero circulations for a desired set of cycles in . These cycles will not appear in . We will keep eliminating cycles in this way until we obtain a w such that Gw has no cycles. Recall that Gw is defined to be the union of minimum weight perfect matchings with respect to w, and thus, contains at least one perfect matching. Since Gw has no cycles, it must have a unique perfect matching, and so, w is isolating for G. Figure 3 shows a graph where an isolating weight assignment is constructed in 3 rounds using our Approach 1, described below.

Bound on the weights. If we want to assign nonzero circulations to at most s cycles in each round, then the weights are bounded by ms by Lemma 3. 1. If there are k such rounds, the bound on the weights becomes O( (nms)k). As we will see later, the quantity (nms)k will be quasi-polynomially bounded.

Recall that Lemma 3. 1 gives a list of ms candidate weight functions such that at least one of them gives nonzero circulations to all the s cycles chosen in a round. We need to try all possible (ms)k combinations of these candidate functions coming from each round. Our quasi-NC algorithm tries all these combinations in parallel.

Now, the crucial question left in our isolating weight
construction is this: how to eliminate all cycles, which are
edges present in a perfect matching, that is, the weight of a
perfect matching.

An important point to note here is that the above LP formulation works only for bipartite graphs, and this is the reason our proof does not work for general graphs.

From the standard theory of LP duality, the following is the dual linear program for minimum weight perfect matching. Since in the primal LP above we had an equality constraint for each vertex, here we have a variable for each vertex.

( 3)

Note that the dual variables do not have any non-negativity constraint, since the primal constraints are equalities.

It follows from strong LP duality that the optimal values of these two linear programs are equal. This will be crucial for the proof of Lemma 2. 1.

Proof of Lemma 2. 1. Let e = (u, v) be any edge participating
in a minimum weight perfect matching, in other words, e is
an edge in Gw. Let y ∈ V be a dual optimal solution. We claim
that the dual constraint ( 3) corresponding to e is tight, that
is,
( 4)

This can be seen as follows: for any minimum weight perfect
matching M, its weight by definition is the primal optimal
value, and thus, by strong duality must be equal to the dual
optimal value. That is,
Note that a sum over all vertices is the same as a sum over
the end points of all the edges in a perfect matching. Thus,
( 5)

Together with ( 3), Equation ( 5) implies Equation ( 4).

Now, let C = (u1, u2, …, u2k) be a cycle in Gw. Since each edge in C is part of some minimum weight perfect matching, by ( 4), all the edges of C are tight w.r.t. the dual optimal solution y. Hence, Hence, every cycle in Gw has zero circulation. 

3. CONSTRUCTING AN ISOLATING WEIGHT
ASSIGNMENT

Corollary 2. 2 gives us a way to eliminate cycles. Suppose C is a cycle in graph G. If we construct a weight assignment w such that circw(C) ≠ 0 then the cycle C will not be present in Gw, that is, at least one edge of C will be missing.

We will be applying this technique on a small set of chosen cycles. As mentioned earlier, there are standard