Resumen: Finding an independent set of maximum size is a NP-hard task on fixed graphs, and can take an exponentially long-time for optimal stochastic algorithms like Glauber dynamics with high activation rates. However, simple algorithms of polynomial complexity seem to perform well in some instances. We studied the large graph characteristics of two simple algorithms in terms of functional law of large numbers and large deviations. We are especially interested in characterizing a phase transition on the “graph landscape”, implying that some simple algorithms are asympotically optimal for low connectivity and suboptimal for high connectivity. Based on a joint works with David García-Zelada, Alon Nishry and Aron Wennman.