The ACO Seminar (2012-2013)

A 2-matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2-matching U is the number of edges in U, and this is at least n - k(U) where n is the number of vertices of G and k denotes the number of components. The algorithm 2GREEDY is a greedy algorithm due to Frieze which finds a maximal 2-matching in a graph. This algorithm is similar to the well known Karp-Sipser algorithm, which finds ordinary matchings in graphs. We analyze the performance of 2GREEDY on a random 3-regular graph. Our analysis yields (more-or-less) matching upper and lower bounds on the final number of components. In particular, we prove that with high probability, the algorithm outputs a 2-matching U with k(U) = n^(1/5 + o(1)).