کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420559 | 683956 | 2009 | 14 صفحه PDF | دانلود رایگان |

In this paper we analyze several approaches to the Maximum Independent Set (MIS) problem in hypergraphs with degree bounded by a parameter ΔΔ. Since independent sets in hypergraphs can be strong and weak, we denote by MIS (MSIS) the problem of finding a maximum weak (strong) independent set in hypergraphs, respectively. We propose a general technique that reduces the worst case analysis of certain algorithms on hypergraphs to their analysis on ordinary graphs. This technique allows us to show that the greedy algorithm for MIS that corresponds to the classical greedy set cover algorithm has a performance ratio of (Δ+1)/2(Δ+1)/2. It also allows us to apply results on local search algorithms on graphs to obtain a (Δ+1)/2(Δ+1)/2 approximation for the weighted MIS and (Δ+3)/5−ϵ(Δ+3)/5−ϵ approximation for the unweighted case. We improve the bound in the weighted case to ⌈(Δ+1)/3⌉⌈(Δ+1)/3⌉ using a simple partitioning algorithm. We also consider another natural greedy algorithm for MIS that adds vertices of minimum degree and achieves only a ratio of Δ−1Δ−1, significantly worse than on ordinary graphs. For MSIS, we give two variations of the basic greedy algorithm and describe a family of hypergraphs where both algorithms approach the bound of ΔΔ.
Journal: Discrete Applied Mathematics - Volume 157, Issue 8, 28 April 2009, Pages 1773–1786