Department Seminar Series
Maximal Independent Sets in Distributed Graphs
6th May 2025, 13:00
Ashton Lecture Theatre
Duncan Adamson
University of St Andrews
Abstract
In this talk, 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 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 $(\alpha, \beta)$-independent sets where the independent set is $\beta$-weak, and each vertex belongs to at least one edge with at least $\alpha$ vertices in the independent set. Finally, we consider the problem of finding a $(2, k)$-ruling set on hypergraphs, i.e. independent sets where no vertex is a distance of more than $k$ from the nearest member of the set.
Given a hypergraph $H$ of rank $r$ and maximum degree $\Delta$, we provide a LLL formulation for finding an $(\alpha, \beta)$-independent set when $(\beta - \alpha)^2 / (\beta + \alpha) \geq 6 \log(16 r \Delta)$, an $O(\Delta r / (\beta - \alpha + 1) + \log^* n)$ round deterministic algorithm finding an $(\alpha, \beta)$-independent set, and a $O(\Delta^2(r - k) \log r + \Delta \log r \log^* r + \log^* n)$ round algorithm for finding a $k$-weak maximal independent set. Additionally, we provide zero round randomized algorithms for finding $(\alpha, \beta)$ independent sets, when $(\beta - \alpha)^2 / (\beta + \alpha) \geq 6 c \log n + 6$ for some constant $c$, and finding an $m$-weak independent set for some $m \geq r / 2k$ where $k$ is a given parameter.