Approximating independent set in semi-random graphs

Bodo Manthey, Kai Plociennik

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

26 Downloads (Pure)

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 languageUndefined
Title of host publicationProceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2010)
EditorsU. Faigle, R. Schrader, D. Herrmann
Place of PublicationCologne, Germany
PublisherUniversity of Cologne
Pages119-122
Number of pages4
ISBN (Print)not assigned
Publication statusPublished - 2010
Event9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010 - University of Cologne, Cologne, Germany
Duration: 25 May 201027 May 2010

Publication series

Name
PublisherUniversity of Cologne

Workshop

Workshop9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2010
CountryGermany
CityCologne
Period25/05/1027/05/10

Keywords

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

Cite this