Communications of the ACM

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

2

1

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.