AbstractFinding maximum independent sets in graphs with bounded maximum degree Delta is a well-studied NP-complete problem. We introduce an algorithm schema for improving the approximation of algorithms for this problem, which is based on preprocessing the input by removing cliques.
We give an implementation of a theorem on the independence number of clique-free graphs, and use it to obtain an O(Delta/loglog Delta) performance ratio with our schema. This is the first o(Delta) ratio for the independent set problem. We also obtain an efficient method with a Delta/6 (1 + o(1)) performance ratio, improving on the best performance ratio known for intermediate values of Delta.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: analysis of algorithms, approximation algorithms, independent sets
Selected papers that cite this one
- Claudia Bertram-Kretzberg and Hanno Lefmann. The algorithmic aspects of uncrowded hypergraphs (extended abstract). In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 296-304, New Orleans, Louisiana, 5-7 January 1997.
- Thomas Hofmeister and Hanno Lefmann. Independent sets in graphs with triangles. Information Processing Letters, 58(5):207-210, 10 June 1996.
Selected references
- Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and hardness of approximation problems. In 33rd Annual Symposium on Foundations of Computer Science, pages 14-23, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE.
- Mihir Bellare and Madhu Sudan. Improved non-approximability results. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 184-193, Montréal, Québec, Canada, 23-25 May 1994.
- Magnús M. Halldórsson and Jaikumar Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 439-448, Montréal, Québec, Canada, 23-25 May 1994.
- Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh Vazirani. On syntactic versus computational views of approximability. In 35th Annual Symposium on Foundations of Computer Science, pages 819-830, Santa Fe, New Mexico, 20-22 November 1994. IEEE.