License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.48
URN: urn:nbn:de:0030-drops-181002
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18100/
Go to the corresponding LIPIcs Volume Portal

Dorobisz, Andrzej ; Kozik, Jakub

Local Computation Algorithms for Hypergraph Coloring - Following Beck’s Approach

pdf-format:
LIPIcs-ICALP-2023-48.pdf (0.8 MB)

Abstract

We investigate local computation algorithms (LCA) for two-coloring of k-uniform hypergraphs. We focus on hypergraph instances that satisfy strengthened assumption of the Lovász Local Lemma of the form 2^(1-αk) (Δ+1) e < 1, where Δ is the bound on the maximum edge degree. The main question which arises here is for how large α there exists an LCA that is able to properly color such hypergraphs in polylogarithmic time per query. We describe briefly how upgrading the classical sequential procedure of Beck from 1991 with Moser and Tardos' Resample yields polylogarithmic LCA that works for α up to 1/4. Then, we present an improved procedure that solves wider range of instances by allowing α up to 1/3.

BibTeX - Entry

@InProceedings{dorobisz_et_al:LIPIcs.ICALP.2023.48,
  author =	{Dorobisz, Andrzej and Kozik, Jakub},
  title =	{{Local Computation Algorithms for Hypergraph Coloring - Following Beck’s Approach}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{48:1--48:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18100},
  URN =		{urn:nbn:de:0030-drops-181002},
  doi =		{10.4230/LIPIcs.ICALP.2023.48},
  annote =	{Keywords: Local Computation Algorithms, Hypergraph Coloring, Property B}
}

Keywords: Local Computation Algorithms, Hypergraph Coloring, Property B
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI