Greedy algorithms for random regular graphs
Michail Beis · 2006
In this thesis we examine problems concerned with the existence of sets of vertices or edges satisfying certain properties in random r-regular graphs. Our approach to those problems is mostly algorithmic. The method used for the analysis of our algorithms is the differential equation method which is due to Wormald. In this method one associates with a particular algorithm a sequence of random processes indexed by some parameter n (which is usually the number of vertices in the initial graph of the process) and defines an additional number of random variables to describe some interesting features of the processes. The aim is the investigation of the most likely values of these variables when the parameter n becomes large. Theoretical results imply that the dynamics of these random systems are approximated with overwhelming probability, by the solutions to a set of differential equations. This is attained by assuring that certain requirements for the random processes are satisfied, which allows treating the random variables as continuous and consequently expressing the differential equations derived from their expected changes. Therefore one can infer that although the quantities of interest are random in general, for large values of n, they are sharply concentrated around a particular (deterministic) value. The problems that have been considered are the maximum k-separated matching, the maximum k-independent set and the maximum k-separated l-path. For each one of those, greedy algorithms for approximating their solution have been constructed and their average-case performance has been analysed using the differential equation method, thus obtaining almost sure lower bounds on the quantity of interest. Furthermore, combinatorial almost sure upper bounds have been proven using direct expectation arguments.