Scholarlink

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 \((\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. Given a hypergraph H of rank r and maximum degree \(\varDelta \) , we provide a LLL formulation for finding an \((\alpha , \beta )\) -independent set when \((\beta - \alpha )^2 / (\beta + \alpha ) \ge 6 \log (16 r \varDelta )\) , an \(O(\varDelta r / (\beta - \alpha + 1) + \log ^* n)\) round deterministic algorithm finding an \((\alpha , \beta )\) -independent set, and a \(O(\varDelta ^2(r - k) \log r + \varDelta \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 ) \ge 6 c \log n + 6\) for some constant c, and finding an m-weak independent set for some \(m \ge r / 2k\) where k is a given parameter. Finally, we provide lower bounds of \(\varOmega (\varDelta + \log ^* n)\) and \(\varOmega (r + \log ^* n)\) on the problems of finding k-weak maximal independent sets for some values of k.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Distributed Weak Independent Sets in Hypergraphs: Upper and Lower Bounds

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Duncan Adamson,
  • Will Rosenbaum,
  • Paul G. Spirakis

摘要

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 \((\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. Given a hypergraph H of rank r and maximum degree \(\varDelta \) , we provide a LLL formulation for finding an \((\alpha , \beta )\) -independent set when \((\beta - \alpha )^2 / (\beta + \alpha ) \ge 6 \log (16 r \varDelta )\) , an \(O(\varDelta r / (\beta - \alpha + 1) + \log ^* n)\) round deterministic algorithm finding an \((\alpha , \beta )\) -independent set, and a \(O(\varDelta ^2(r - k) \log r + \varDelta \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 ) \ge 6 c \log n + 6\) for some constant c, and finding an m-weak independent set for some \(m \ge r / 2k\) where k is a given parameter. Finally, we provide lower bounds of \(\varOmega (\varDelta + \log ^* n)\) and \(\varOmega (r + \log ^* n)\) on the problems of finding k-weak maximal independent sets for some values of k.