Partial covering of hypergraphs
Özgür Sümer · Symposium on Discrete Algorithms · 2005
Let H be a hypergraph with m edges and maximum degree Δ. Given e ≥ 0, a (1 - e)-vertex-cover is a collection T of vertices which hits at least (1 - e)m edges. We denote min |T| by τe. Note that T = To is the (full) covering number of H.In this paper we study the performance ratio of the greedy algorithm for this vertex cover problem and compare it to random choice and to optimal fractional cover. For the first time, we prove a performance ratio bound depending only on e > 0 for an important class of hypergraphs.Let T* be the optimal fractional covering number (e = 0). Lovasz (1975) showed that To ≤ (1 + In Δ)T*, where Δ is the maximum degree, using the greedy algorithm; it follows that the greedy algorithm has performance ratio ≤ 1 + In Δ.Kearns (1990) introduced the partial vertex problem. He proved that the performance ratio of the greedy algorithm for the partial vertex problem is ≤ 5+2 In m regardless of e ≥ 0. Later, Slavik (1997a) improved the bound to 1 + In Δ. Kearns' and Slavik's bounds apply to weighted hypergraphs; in this paper we study the unweighted case only.Our main result is that for e > 0, the performance ratio of the greedy algorithm is ≤ 1 + In(ΔT*/em). As a corollary, we confirm Babai's conjecture that the greedy algorithm has a performance ratio ≤ 1+In(1/e) for regular and uniform hypergraphs. This special case has significant applications. On the other hand we present examples in which the performance ratio reaches In Δ if either one of the conditions of regularity and uniformity is dropped.We also show that the ratio of the greedy (1 - e)-cover to T* is ≤ 1/e for all hypergraphs. Note that this bound again does not depend on the parameters of the hypergraph and is the first such bound.We demonstrate the tightness of our bounds by presenting examples of regular and uniform hypergraphs that have performance ratio ≥ In(1/e) for partial vertex covering. We obtain similar matching upper and lower bounds for the integrality gap of partial covering.We compare the bounds attained by the greedy algorithm with random choice. We establish a counterintuitive gap of In(1/e) in favor of random choice for a class of regular and uniform hypergraphs.