Distributed Weak Independent Sets in Hypergraphs: Upper and Lower Bounds

Adamson, D ORCID: 0000-0003-3343-2435, Rosenbaum, W ORCID: 0000-0002-7723-9090 and Spirakis, PG ORCID: 0000-0001-5396-3749 (2026) Distributed Weak Independent Sets in Hypergraphs: Upper and Lower Bounds In: ALGOWIN-ALGO2025, 2025-9-18 - 2025-9-19, Warsaw Poland.

Text Distributed_Weak_Maximal_Independent_Sets.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (472kB) | Preview

Abstract

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.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	46 Information and Computing Sciences
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	04 Aug 2025 09:10
Last Modified:	24 Jan 2026 05:25
DOI:	10.1007/978-3-032-09120-8_1
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3193902
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.