Large graph limits of local matching algorithms on uniform random graphs
Résumé
In this work, we propose a large-graph limit estimate of the matching coverage for several matching algorithms, on general graphs generated by the configuration model. For a wide class of local matching algorithms, namely, algorithms that only use information on the immediate neighborhood of the explored nodes, we propose a joint construction of the graph by the configuration model, and of the resulting matching on the latter graph. This leads to a generalization in infinite dimension of the differential equation method of Wormald: We keep track of the matching algorithm over time by a measure-valued CTMC, for which we prove the convergence, to the large-graph limit, to a deterministic hydrodynamic limit, identified as the unique solution of a system of ODE's in the space of integer measures. Then, the asymptotic proportion of nodes covered by the matching appears as a simple function of that solution. We then make this solution explicit for three particular local algorithms: the classical greedy algorithm, and then the uni-min and uni-max algorithms, two variants of the greedy algorithm that select, as neighbor of any explored node, its neighbor having the least (respectively largest) residual degree.
Domaines
Mathématiques [math]Origine | Fichiers produits par l'(les) auteur(s) |
---|