Approximating independent set in perturbed graphs

Bodo Manthey, Kai Plociennik

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
78 Downloads (Pure)


For the maximum independent set problem, strong inapproximability bounds for worst-case efficient algorithms exist. We give a deterministic algorithm beating these bounds, with polynomial expected running-time for semi-random graphs: An adversary chooses a graph with $n$ vertices, and then edges are flipped with a probability of $\varepsilon$. Our algorithm guarantees an approximation ratio of $O(\sqrt{n\varepsilon})$ for sufficiently large $\varepsilon$.
Original languageEnglish
Pages (from-to)1761-1768
Number of pages8
JournalDiscrete applied mathematics
Issue number12
Publication statusPublished - 2013


  • Smoothed Analysis
  • IR-85610
  • Independent set
  • EWI-20770
  • METIS-296419
  • Random graphs
  • Semi-random graphs


Dive into the research topics of 'Approximating independent set in perturbed graphs'. Together they form a unique fingerprint.

Cite this