A note on the Greedy algorithm for finding independent sets of C-k-free graphs
The independent set problem is known to be NP-hard. A fundamental theorem of Turan [P. Turan, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436-452] states that any graph with n vertices and average degree (d) over bar contains an independent set of size at least n/((d) over bar + 1), which is known as Turan bound. The greedy algorithm with minimum-degree pivoting rule is well-known method for attaining Turan bound. Based on this result, Hochbaum [D.S. Hochbaurn, 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 ((d) over bar + 1)/2. This paper shows that if the input graph is assumed to be C-k-free then the greedy algorithm obtains an independent set of size at least 2n/((d) over bar + 1 + k). It also proves that the LP-based algorithm has the performance ratio ((d) over bar + 1 + k)/4. (C) 2009 Elsevier B.V. All rights reserved.
approximation algorithms analysis of algorithms maximum independent set