AbstractA graph is d-claw free if no node has d distinct independent neighbors. In the most usual applications, the nodes of this graph form a family of sets with fewer than d elements, and the edges indicate overlapping pairs of sets. Consequently, an independent set in the graph is a packing in our family of sets. In this paper we consider the following problem. Given is a d-claw free graph G = (V,E,w) where w: V -> R+. We describe an algorithm with running time polynomial in |V|d that finds an independent set A such that w(A*)/w(A) <= d/2, where A* is an independent that maximizes w(A*). The previous best polynomial time approximation algorithm obtained w(A*)/w(A) <= 2d/3.
Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: approximation algorithms, maximum independent set, node weights
Selected references
- Magnús M. Halldórsson. Approximating discrete collections via local improvements. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 160-169, San Francisco, California, 22-24 January 1995.