Distributed weak independent sets in hypergraphs: upper and lower bounds

In this paper, we consider the problem of finding weak independent sets in a distributed network represented by a hypergraph. In this setting, each edge contains a set of r vertices rather than simply a pair, as in a standard graph. A k-weak independent set in a hypergraph is a set where no edge contains more than k vertices in the independent set. We focus on two variations of this problem. First, we study the problem of finding k-weak maximal independent sets, k-weak independent sets where each vertex belongs to at least one edge with k vertices in the independent set. Second we introduce a weaker variant that we call (α,β)-independent sets where the independent set is β-weak, and each vertex belongs to at least one edge with at least α vertices in the independent set. Given a hypergraph H of rank r and maximum degree Δ, we provide a LLL formulation for finding an (α,β)-independent set when (β-α)²/(β+α)≥6log(16rΔ), an O(Δr/(β-α+1)+log^∗n) round deterministic algorithm finding an (α,β)-independent set, and a O(Δ²(r-k)logr+Δlogrlog^∗r+log^∗n) round algorithm for finding a k-weak maximal independent set. Additionally, we provide zero round randomized algorithms for finding (α,β) independent sets, when (β-α)²/(β+α)≥6clogn+6 for some constant c, and finding an m-weak independent set for some m≥r/2k where k is a given parameter. Finally, we provide lower bounds of Ω(Δ+log^∗n) and Ω(r+log^∗n) on the problems of finding k-weak maximal independent sets for some values of k.