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