Approximating the minimum independent dominating set in perturbed graphs

We investigate the minimum independent dominating set in perturbed graphs g(G,p)g(G,p) of input graph G=(V,E)G=(V,E), obtained by negating the existence of edges independently with a probability p>0p>0. The minimum independent dominating set (MIDS) problem does not admit a polynomial running time approximation algorithm with worst-case performance ratio of n1−ϵn1−ϵ for any ϵ>0ϵ>0. We prove that the size of the minimum independent dominating set in g(G,p)g(G,p), denoted as i(g(G,p))i(g(G,p)), is asymptotically almost surely in Θ(log⁡|V|)Θ(log⁡|V|). Furthermore, we show that the probability of i(g(G,p))⩾4|V|p is no more than 2−|V|2−|V|, and present a simple greedy algorithm of proven worst-case performance ratio 4|V|p and with polynomial expected running time.