Abstract
Finding maximum independent sets in graphs with bounded maximum degree is a well-studied NP-complete problem. We study two approaches for finding approximate solutions, and obtain several improved performance ratios.
The first is a subgraph removal schema introduced in our previous paper. Using better component algorithms, we obtain an efficient method with a Δ/6(1+o(1)) performance ratio. We then produce an implementation of a theorem of Ajtai et al. on the independence number of clique-free graphs, and use it to obtain a O(Δ/loglogΔ) performance ratio with our schema. This is the first o(Δ) ratio.
The second is a local search method of Berman and Fürer for which they proved a fine performance ratio but by using extreme amounts of time. We show how to substantially decrease the computing requirements while maintaining the same performance ratios of roughly (Δ+3)/5 for graphs with maximum degree Δ. We then show that a scaled-down version of their algorithm yields a (Δ+3)/4 performance, improving on previous bounds for reasonably efficient methods.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Ajtai, P. Erdős, J. Komlós, and E. Szemerédi. On Turán's theorem for sparse graphs. Combinatorica, 1(4):313–317, 1981.
M. Ajtai, J. Komlós, and E. Szemerédi. A note on Ramsey numbers. J. Combin. Theory Ser. A, 29:354–360, 1980.
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and intractability of approximation problems. In Proc. 33nd IEEE Symp. on Found. of Comp. Sci., pages 14–23, Oct. 1992.
M. Bellare and M. Sudan. Improved non-approximability results. To appear in STOC '94, May 1994.
P. Berman and M. Purer. Approximating maximum independent set in bounded degree graphs. In Proc. Fifth ACM-SIAM Symp. on Discrete Algorithms, Jan. 1994.
R. B. Boppana and M. M. Halldórsson. Approximating maximum independent sets by excluding subgraphs. BIT, 32(2):180–196, June 1992.
P. Erdős. Some remarks on chromatic graphs. Colloq. Math., 16:253–256, 1967.
M. M. Halldórsson and J. Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. To appear in STOC '94, May 1994.
D.S. Hochbaum. Efficient bounds for the stable set, vertex cover, and set packing problems. Disc. Applied Math., 6:243–254, 1983.
S. Khanna, R. Motwani, M. Sudan, and U. Vazirani. On syntactic versus computation views of approximability. Manuscript, Dec. 1993.
C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity. J. Comput. Syst. Sci., 43:425–440, 1991.
J. B. Shearer. A note on the independence number of triangle-free graphs. Discrete Math., 46:83–87, 1983.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Halldórsson, M.M., Radhakrishnan, J. (1994). Improved approximations of independent sets in bounded-degree graphs. In: Schmidt, E.M., Skyum, S. (eds) Algorithm Theory — SWAT '94. SWAT 1994. Lecture Notes in Computer Science, vol 824. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58218-5_18
Download citation
DOI: https://doi.org/10.1007/3-540-58218-5_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58218-2
Online ISBN: 978-3-540-48577-3
eBook Packages: Springer Book Archive