Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438179 | Theoretical Computer Science | 2014 | 8 Pages |
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.