|
Abstract: |
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 - e} for any e > 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 Theta(log |V|). Furthermore, we show that the probability of i(g(G, p)) >= sqrt{4|V|/p} is no more than 2^{-|V|}, and present a simple greedy algorithm of proven worst-case performance ratio sqrt{4|V|/p} and with polynomial expected running time. |
