In this paper, we study Ranking, a well-known randomized greedy matching algorithm, for general graphs. The algorithm was originally introduced by Karp, Vazirani, and Vazirani [STOC 1990] for the online bipartite matching problem with one-sided vertex arrivals, where it achieves a tight approximation ratio of \(1 -1/e\). It was later extended to bipartite graphs with random vertex arrivals by Mahdian and Yan [STOC 2011] and to general graphs by Goel and Tripathi [FOCS 2012]. The Ranking algorithm for general graphs is as follows: a permutation \(\sigma\) over the vertices is chosen uniformly at random. The vertices are then processed sequentially according to this order, with each vertex being matched to the first available neighbor (if any) according to the same permutation \(\sigma\).

Randomized greedy algorithms form one of the simplest yet most effective approaches for computing approximate matchings in graphs. In this paper, we focus on the class of vertex-iterative (VI) randomized greedy matching algorithms, which process the vertices of a graph G=(V,E) in some order π and, for each vertex v, greedily match it to the first available neighbor (if any) according to a preference order σ(v). Various VI algorithms have been studied, each corresponding to a different distribution over π and σ(v).