Embracing the giant component

Abstract

Consider a game in which edges of a graph are provided a pair at a time, and the player selects one edge from each pair, attempting to construct a graph with a component as large as possible. This game is in the spirit of recent papers on avoiding a giant component, but here we embrace it. We analyze this game in the offline and online setting, for arbitrary and random instances, which provides for interesting comparisons. For arbitrary instances, we find that the competitive ratio (the best possible solution value divided by best possible online solution value) is large. For "sparse" random instances the competitive ratio is also large, with high probability (whp); If the instance has 1/4(1 + ε)n random edge pairs, with 0 < ε ≤ 0.003, then any online algorithm generates a component of size O((log n) 3/2) whp, while the optimal offline solution contains a component of size Ω(n) whp. For "dense" random instances, the average-case competitive ratio is much smaller. If the instance has 1/2(1 - ε)n random edge pairs, with 0 < ε ≤ 0.015, we give an online algorithm which finds a component of size Ω(n) whp. © 2005 Wiley Periodicals, Inc.