The following lemma about circulations of cycles gives
us a way to eliminate cycles. For a weight assignment w on
the edges of a graph G, let Gw be the union of minimum
weight perfect matchings, that is, it is a subgraph of G that
has exactly those edges that are present in some minimum
weight perfect matching in G.
Lemma 2. 1 (Zero circulation). Let w be a weight function
on the edges of a bipartite graph G. Let C be a cycle in the subgraph Gw. Then circw(C) = 0.
The following corollary is immediate, which shows how
the above lemma can be used to eliminate cycles.
Corollary 2. 2 (Cycle elimination). Let C be a cycle in a
bipartite graph G and w be a weight function on its edges such
that circw(C) ≠ 0. Then C is not present in Gw.
There are several ways to prove Lemma 2. 1.
1. In our original article,
10 we presented a proof based
on properties of the perfect matching polytope. In the
argument, the center point of the polytope is slightly
moved along cycle C, so that the point stays in the
polytope. This implies that the circulation of C must
2. After the first version of our article was published,
Rao, Shpilka, and Wigderson (see [Goldwasser and
13 Lemma 2. 4]) came up with an alternate
proof of Lemma 2. 1, similar to ours, but based on
Hall’s Theorem instead of the matching polytope.
3. In a column for SIGACT News,
11 we gave a geometric
proof, where we just argue via vectors being parallel or
perpendicular to each other. One might consider this
the shortest and most elegant of the proofs.
4. Nevertheless, in Section 2. 1 below, we present a fourth
proof that we find very nice. It is based on LP duality.
2. 1. LP formulation for perfect matching
The minimum weight perfect matching problem on bipartite graphs has a simple and well-known LP formulation.
Let G be a bipartite graph with vertex set V and edge set E.
Then the following linear program captures the minimum
weight perfect matching problem (see, for example, Lovász
where d(v) denotes the set of edges incident on a vertex v.
The linear program has one variable xe for each edge in the
graph. Intuitively, xe = 1 represents that the edge e is present
in the perfect matching and xe = 0 represents that e is not
in the perfect matching. Then, Equation ( 2) is simply saying that a perfect matching contains exactly one edge from
the set of edges incident on a particular vertex. The objective function asks to minimize the sum of the weights of the
1. In the first approach, in the ith round, we eliminate all
cycles of length at most 2i+ 1. Hence, we eliminate all
cycles in log n rounds. Each round is efficient because
if a graph does not have any cycles of length at most ,
then the number of cycles up to length 2 is polynomially bounded.
2. In the second approach, first we eliminate all cycles of
length at most 4 log n. The bound we have on the number of such cycles is quasi-polynomial in n. Alon, Hoory,
and Linial2 have shown that any graph which does not
contain any cycle of length ≤
4 log n must have average
degree at most 2. 5, and thus must have at least a constant fraction of nodes with degree 2 or less. From the
resulting graph, we remove all nodes of degree 1, and
we contract degree- 2 nodes one by one (identifying the
two neighbors), until there are no degree- 2 nodes left.
This creates new small cycles in the graph. We then
repeat the procedure of eliminating cycles of length at
most 4 log n from the new graph. In each round the
number of nodes decreases by a constant fraction.
Thus, after O(log n) rounds, we eliminate all nodes and
hence, all cycles.
3. In the third approach, instead of considering the
lengths of the cycles, we try to pick as many edge-disjoint cycles as possible and eliminate them. Note that
edge-disjointness ensures that we will eliminate at
least as many edges as cycles. Erdös and Pósa9 showed
that any graph with m edges and n nodes contains
edge-disjoint cycles. A careful argument
shows that in O(log2 n) rounds, we eliminate enough
edges so that no cycles are left.
As we will see later, the first approach is more efficient than
the other two. We still think it is interesting to see different
ways of achieving isolation, as they might lead to better ideas
for getting isolation with polynomially bounded weights
or isolation in other settings. Another interesting point is
that our second approach was used in designing a
pseudo-deterministic RNC algorithm for bipartite matching.
Our crucial technical result (Lemma 2. 1) about eliminating cycles has a proof based on linear programming (LP)
duality. In the next section, we describe a LP formulation for
bipartite perfect matching and its dual, and then use it to
prove our result. Finally in Section 3, we formally describe
the weight construction and the three approaches to eliminate all cycles.
2. CYCLE ELIMINATION VIA NONZERO CIRCULATIONS
In this section, we formally describe our main technical tool
which enables cycle elimination. Let us first give a formal
definition of cycle circulation. For a weight assignment w
on the edges of a graph G, the circulation circw(C) of an even-length cycle C = (v1, v2, ..., vk) is defined as the alternating
sum of the edge weights around C:
The definition is independent of the edge we start with
because we take the absolute value of the alternating sum.