Embracing the giant component
There has been interest in recent years in situations where a collection of random pairs of edges of a graph is given, one pair at a time, and the object is to select one edge from each pair in order to avoid forming a giant component in the graph. (If the pairs consist of two edges selected at random, and then one of them is chosen at random, then \textbf{whp} (that is, with probability tending to 1 as \(n\rightarrow\infty\)) a component whose size is linear in the number \(n\) of vertices will exist when a total of about \(n/2\) edges have been selected.) It is equally natural to investigate whether, when one has \((1-\varepsilon)n/2\) edges, there is some strategy for encouraging a giant component to form. More precisely, we define the problem EGC (embracing the giant component) by saying that an instance I consists of a sequence of \(m\) pairs of edges on \(n\) vertices. (Edges may repeat, and \` pairs\'\, may be the same edge.) A solution is a choice of one edge from each pair, and the value of a solution is the order of the largest component of the graph on \(n\) vertices with these \(m\) (or fewer if there are repeats) edges. The object is to maximise the value of I. Both online cases (i.e. we select our edge from the \(i\)th pair before seeing the \((i+1)\)th pair) and offline versions (where all pairs are visible throughout) are studied: a recurring theme is how badly online methods do compared with offline ones (but see Theorem 6 below). The first case studied is worst-case. It is shown that, for any online algorithm, there is a sequence of \(m\) edge pairs for which the algorithm generates a collection of isolated edges (i.e. the largest component has order 2) but there is in fact an optimal solution with \(m+1\) vertices. This is done by considering a complete binary tree. This argument is based on an adversarial approach, but there is a similar result for the case of random choices by the online algorithm, based on the fact that it only has probability 1/2 of selecting the right edge at each stage, so will only generate a component of order \(O(\log(n))\). The authors also show, by a reduction to 3-SAT, that the offline EGC is hard to approximate beyond a (problem-dependent) fixed factor (unless P = NP): technically, offline EGC is MAX-SNP hard. The main work of the paper is an average case result. We define \(I_{n,m}\) to be a random instance of EGC in which each edge of the pair is chosen independently, uniformly at random from the edge set of the complete graph \(K_{n}\). The key idea is to show that there is a (sharp) threshold for the random instances at \(m=n/4\). The proof relies on a \` component-revealing algorithm\'\, \({\mathcal A}\) proceeding roughly as follows. We maintain two sets of vertices, the unborn ones \(U_{i}\) and the alive ones \(A_{i}\) at stage \(i\). Initially \(A_{1}\) consists of a single vertex \(v_{1}\) and \(U_{1}=[n]\backslash v_{1}\). At step \(i\), look at all neighbours of some \(v_{i}\in A_{i}\): kill \(v_{i}\) and declare all its (previously unborn) neighbours to be born. Essentially this leads to a proof of Theorem 4 (misprinted in the paper): in correct form, it states that if \(m=(1-\varepsilon)n/4\) we have EGC(\(I_{n,m})=O(\log(n))\) (this is trivial from the classical Erdős-Rényi results) but if \(m=(1/4+\varepsilon)n\) a greedy heuristic similar to \({\mathcal A}\) (try starting at each vertex, and use the first edge we see from each pair) will give a giant component in offline EGC(\(I_{n,m})\). As just noted, the result for \(m=(1/4+\varepsilon)n\) is the hard work: the two key steps are to observe that, with a precise form of the algorithm \({\mathcal A}\) (called \({\mathcal B}\)) the algorithm either stops before a certain time whose order of magnitude in \(n\) is \(\log(n)\), or continues to after some time whose order of magnitude is linear in \(n\), and also to note that \textbf{whp} there is some vertex \(v\) from which \({\mathcal B}\) gives a component of at least logarithmic size (which it then extends to a component whose order is linear in \(n\)). The other main result is that, for random instances only slightly above the threshold, every online algorithm only finds small components (so again the online case is much worse than the offline one). Indeed for \(\varepsilon\leq 0.003\) on instances \(I_{n,m}\) the algorithm only finds a component of size only \(O(\log(n)^{3/2})\) \textbf{whp}. In fact this part of the argument is conducted for a more general class of algorithms. The rough idea is that we give the algorithm the first \(\gamma n\) pairs, allow it a very generous opportunity to form components with at least 2 edges, and only required it to choose a subset of \(\gamma n\) of the isolated edges: the rough idea is now that if the first \(\gamma(n)\) edges were all isolated, the graph would (after the first stage) consist of \(\gamma n\) edges, then the final graph would be a union of a random matching of size \(\gamma n\) and \(2(1/4(1+\varepsilon)-\gamma)n\) random edges, which is \` morally\'\, equivalent to a graph with \((1+\varepsilon-2\gamma)n/2\) random edges, below the threshold for a giant. Turning this intuition into rigorous mathematics requires a lot of work, including a tree census result for sparse random graphs and the Azuma-Hoeffding inequality. The authors finish by showing a result (Theorem 6) in the other direction. If \(\varepsilon\leq 0.015\), a certain algorithm \({\mathcal C}\) \textbf{whp} yields a giant component with \(m=(1-\varepsilon)n/2\). Again a vertex exposure argument is required, together with much calculation.
- The Bohman-Frieze process near criticality
- Delaying satisfiability for random 2SAT
- Getting a directed Hamilton cycle two times faster
- Hamiltonicity thresholds in Achlioptas processes
- Ramsey games with giants
- Random k-SAT and the power of two choices
- Avoiding small subgraphs in Achlioptas processes
- Creating a Giant Component
- Small subgraphs in random graphs and the power of multiple choices
- A phase transition for avoiding a giant component
- Coloring the edges of a random graph without a monochromatic giant component
- LATIN 2004: Theoretical Informatics
- Connected components and evolution of random graphs: An algebraic approach
- Fast construction on a restricted budget
- A geometric Achlioptas process
This page was built for publication: Embracing the giant component
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5704836)