Speaker: Patrick Bennett
Carnegie Mellon University
Title: A greedy algorithm for finding a large 2-matching on a random cubic graph
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)).
Joint work with Deepak Bal, Tom Bohman, and Alan Frieze (all of Carnegie Mellon University).