Feb 28, 3:30pm, Wean 8220

Patrick Bennett, CMU

A greedy algorithm for finding a large 2-matching on a random cubic graph

Patrick Bennett, CMU

A greedy algorithm for finding a large 2-matching on a random cubic graph

Abstract:

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)).