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>0 p > 0 . The minimum independent dominating set (MIDS) problem does not admit a polynomial running time approximation algorithm with worst-case performance ratio of n1?? n 1 ? ? 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.
independent dominating set dominating set perturbed graph approximation algorithm independent set smooth analysis