3. 1. Approach 1: Doubling the lengths of the cycles
Here, the idea is to double the length of the cycles that we
want to eliminate in each round. There will be log n rounds.
In the ith round, we eliminate all cycles of length at most
2i+ 1, and thus we eliminate all cycles in log n rounds. The following lemma shows that if we have already eliminated all
the cycles of length at most 2i then the number of cycles of
length 2i+ 1 is polynomially bounded, for any i.
Lemma 3. 2 (Subramanian23). Let H be a graph with n nodes
that has no cycles of length at most r, for some even number
r ≥ 4. Then H has at most n4 cycles of length at most 2r.
Proof. Let C be a cycle of length ≤2r in G. We choose four
vertices u0, u1, u2, u3 on C, which divide it into four almost
possibly exponentially many, in a small number of rounds,
while only eliminating a small number of cycles in each
round. We present three different approaches for this. Each
approach will have a different criterion for choosing a small
set of cycles, which are to be eliminated in a round. The rest
of the procedure is common to all three approaches. The fol-
lowing table gives, for each approach, the number of cycles
chosen in each round and the number of rounds required to
eliminate all cycles. Here we use m ≤ n2.
Number of cycles
in each round
Number
of rounds Bound on the weights
Approach 1 n4 O(log n) nO(log n)
Approach 2 nO(log n) O(log n) nO(log2 n)
Approach 3O(n2) O(log2n)nO(log2n)
1
1024 512 8
e6 e1 e7 e8
e2
e4 e10 e9 e3
e0 e5 e11
64
2 128 256
4
16
1
32 2048
1
1
2
1
2
2
1
1
2
22
2
2
1
2
24
44
1
4
32
1
4
11
3
42
2
41
1
3
114 222 223 141
121 124 212 213
144 111 242 243
The initial weights are w(ei) := 2i.
Take w(mod 7) . The 6-cycles are gone, but
only e11 is removed in the derived graph—
the union of the blue and red matchings
(the non-min-weight green does not survive).
Take w(mod 5) . The 10-cycle is now gone
and only the blue matching survives in the
derived graph.
Take w(mod 3). The 4-cycles are gone, but
only e5 is removed in the derived graph—the
union of 3 min matchings (blue, red, green).
G is a 10-node graph with 12 edges
e0, . . . , e11.
Combining the reduced weights gives us a
weight function that isolates the blue matching
as unique with min weight. Numbers can be
interpreted in any radix ≥ 5 in this example.
Figure 3. Iterative construction of an isolating weight assignment on a bipartite graph.