# Approximating independent set in perturbed graphs

Bodo Manthey, Kai Plociennik

2 Citations (Scopus)

## Abstract

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 language English 1761-1768 8 Discrete applied mathematics 161 12 https://doi.org/10.1016/j.dam.2012.06.008 Published - 2013

## Keywords

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

## Fingerprint

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