Approximating the independence number and the chromatic number in expected polynomial time (Q1598877)

For a number \(f\geq 1\), we say that an algorithm \(A\) approximates the independence number within factor \(f\) over graphs on \(n\) vertices, if for every such graph \(G\) the algorithm \(A\) outputs an independent set \(I\), whose size satisfies \(|I|\geq \frac{\alpha(G)}{f}\). Similarly, \(A\) approximates the chromatic number within factor \(f\) for graphs on \(n\) vertices if for every such a graph it outputs a colouring with the number of colours \(k\) satisfying \(k\leq f\cdot \chi(G)\). Recent results have shown that in general there is no polynomial time algorithm which approximates these two parameters within a satisfactory factor. In this paper it is shown that the situation is significantly better than in the average case. For an integer \(n\) and a function \(0\leq p=p(n)\leq 1\), the random graph \(G(n,p)\) is a graph with \(n\) labeled vertices \(1,2,\dots, n\), where each pair of vertices \((i,j)\) is chosen to be an edge of \(G\) independently with probability \(p\). Given an algorithm \(A\), whose domain is the set of all graphs on \(n\) vertices, and a probability space \(G(n,p)\), the expected running time of \(A\) over \(G(n,p)\) is defined as \(\sum_{G} Pr[G] R_{A}(G)\) where the sum runs over all labeled graphs on \(n\) vertices, \(Pr[G]\) is the probability that \(G\) is chosen according to the distribution \(G(n,p)\) and \(R_{A}(G)\) stands for the running time of \(A\) on \(G\). It is shown that for \(p=p(n)\) in the range \(n^{\frac{-1}2+\epsilon}\leq p \leq \frac{3}4\) the independence and chromatic number can be approximated by deterministic algorithms whose expected running times are polynomial and their approximation factor is \(O(\frac{(np)^{\frac{1}2}}{\log n})\) and \(O((np)^{\frac{1}2}\log n)\) respectively. The obtained algorithms are based on the greedy colouring algorithm and an application of Talagrand's inequality.