@inproceedings{51614032e12b41febb677c2ecda3b2db,

title = "Approximating the minimum independent dominating set in perturbed graphs",

abstract = "We investigate the minimum independent dominating set in perturbed graphs 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, denoted as, is asymptotically almost surely in Θ(log|V|). Furthermore, we show that the probability of is no more than 2-|V|, and present a simple greedy algorithm of proven worst-case performance ratio and with polynomial expected running time.",

keywords = "approximation algorithm, dominating set, independent dominating set, Independent set, perturbed graph, smooth analysis",

author = "Weitian Tong and Randy Goebel and Guohui Lin",

year = "2013",

doi = "10.1007/978-3-642-38768-5_24",

language = "English",

isbn = "9783642387678",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "257--267",

booktitle = "Computing and Combinatorics - 19th International Conference, COCOON 2013, Proceedings",

note = "19th International Computing and Combinatorics Conference, COCOON 2013 ; Conference date: 21-06-2013 Through 21-06-2013",

}