| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427795 | Information Processing Letters | 2009 | 5 Pages |
The independent set problem is known to be NP-hard. A fundamental theorem of Turán [P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452] states that any graph with n vertices and average degree contains an independent set of size at least , which is known as Turán bound. The greedy algorithm with minimum-degree pivoting rule is well-known method for attaining Turán bound. Based on this result, Hochbaum [D.S. Hochbaum, Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems, in: D.S. Hochbaum (Ed.), Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1997, pp. 94–143] showed that the greedy algorithm combined with LP attains performance ratio . This paper shows that if the input graph is assumed to be Ck-free then the greedy algorithm obtains an independent set of size at least . It also proves that the LP-based algorithm has the performance ratio .
