Approximating the minimum independent dominating set in perturbed graphs

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