TY - JOUR

T1 - Approximating the minimum independent dominating set in perturbed graphs

AU - Tong, Weitian

AU - Goebel, Randy

AU - Lin, Guohui

N1 - Publisher Copyright:
© 2013 Elsevier B.V.

PY - 2014

Y1 - 2014

N2 - 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 n1-ε 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.

AB - 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 n1-ε 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.

KW - Approximation algorithm

KW - Dominating set

KW - Independent dominating set

KW - Independent set

KW - Perturbed graph

KW - Smooth analysis

UR - http://www.scopus.com/inward/record.url?scp=84926278248&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2013.11.010

DO - 10.1016/j.tcs.2013.11.010

M3 - Article

AN - SCOPUS:84926278248

SN - 0304-3975

VL - 554

SP - 275

EP - 282

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -