@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",
}