Approximation algorithms for non-sequential star packing problems

For a positive integer k ≥ 1, a k-star ( k + -star, k − -star, respectively) is a connected graph containing a degree-ℓ vertex and ℓ degree-1 vertices, where ℓ = k ( ℓ ≥ k, 1 ≤ ℓ ≤ k, respectively). The k + -star packing problem is to cover as many vertices of an input graph G as possible using vertex-disjoint k + -stars in G; and given k > t ≥ 1, the k − / t -star packing problem is to cover as many vertices of G as possible using vertex-disjoint k − -stars but no t-stars in G. Both problems are NP-hard for any fixed k ≥ 2. We present a ( 1 + k 2 2 k + 1 ) - and a 3 2 -approximation algorithms for the k + -star packing problem when k ≥ 3 and k = 2, respectively, and a ( 1 + 1 t + 1 + 1 / k ) -approximation algorithm for the k − / t -star packing problem when k > t ≥ 2. They are all local search algorithms and they improve the best known approximation algorithms for the problems, respectively.

Authors

• Mengyuan Hu
• An Zhang
• Yong Chen
• Mingyang Gong
• Guohui Lin

Keywords

• Star packing
• Local search
• Amortization
• Alternating path
• Approximation algorithm