# Approximating independent set in semi-random graphs

Bodo Manthey, Kai Plociennik

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

### Abstract

We present an algorithm for the independent set problem on semi-random graphs, which are generated as follows: An adversary chooses an n-vertex graph, and then each edge is flipped independently with a probability of $\varepsilon > 0$. Our algorithm runs in expected polynomial time and guarantees an approximation ratio of roughly $O(\sqrt{\varepsilon n})$, which beats the inapproximability bounds.
Original language Undefined Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010) U. Faigle, R. Schrader, D. Herrmann Cologne, Germany University of Cologne 119-122 4 not assigned Published - 2010 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010 - University of Cologne, Cologne, GermanyDuration: 25 May 2010 → 27 May 2010

### Publication series

Name University of Cologne

### Workshop

Workshop 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010 Germany Cologne 25/05/10 → 27/05/10

### Keywords

• METIS-275735
• Independent set
• Approximation algorithms
• EWI-18959
• Smoothed Analysis
• Random graphs
• Semi-random graphs
• IR-75055

### Cite this

Manthey, B., & Plociennik, K. (2010). Approximating independent set in semi-random graphs. In U. Faigle, R. Schrader, & D. Herrmann (Eds.), Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010) (pp. 119-122). Cologne, Germany: University of Cologne.