A graph is "triangle-saturated" if it contains no triangle (three mutually connected vertices) but adding any new edge would create one. Think of it as a maximally triangle-free graph: you have avoided all triangles, yet the structure is so tightly packed that there is no room to add another edge without forming one. The question this paper asks is: how efficiently can you build such a structure under a particular kind of constrained randomness?
The setting is called the semi-random graph process. In each step, one vertex is chosen randomly and handed to an algorithm, which then gets to freely pick which other vertex to connect it to. The algorithm is trying to reach triangle-saturation as quickly as possible, measured in the number of rounds needed. The paper studies two versions: an online version where the algorithm decides each connection as the random vertices arrive one by one, and an offline version where the algorithm sees the entire sequence of random vertices upfront before making any choices. The offline version gives the algorithm strictly more power, since it can plan ahead.
The main results are upper and lower bounds on the number of rounds each version of the algorithm needs. The authors show that both versions can achieve triangle-saturation in roughly the same ballpark of rounds, though the exact thresholds differ, and the offline algorithm naturally performs at least as well as the online one. The work contributes to a broader program of understanding what graph properties can be forced quickly under semi-random processes, where the interplay between adversarial choice and genuine randomness makes the analysis considerably more subtle than either a fully random or fully deterministic setting.