Karp–Sipser on Random Graphs with a Fixed Degree Sequence

Source abstract

Let Δ ≥ 3 be an integer. Given a fixed z ∈ + Δ such that z Δ > 0, we consider a graph G z drawn uniformly at random from the collection of graphs with z i n vertices of degree i for i = 1,. . .,Δ. We study the performance of the Karp–Sipser algorithm when applied to G z . If there is an index δ > 1 such that z 1 = . . . = z δ−1 = 0 and δ z δ ,. . .,Δ z Δ is a log-concave sequence of positive reals, then with high probability the Karp–Sipser algorithm succeeds in finding a matching with n ∥ z ∥ 1 /2 − o ( n 1−ε ) edges in G z , where ε = ε (Δ, z ) is a constant.