2026-07-26T12:15:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21000 2024-09-16T06:02:37Z ddc:004 open_access

A Logarithmic Approximation of Linearly-Ordered Colourings Håstad, Johan Martinsson, Björn Nakajima, Tamio-Vesa Živný, Stanislav Linear ordered colouring Hypergraph Approximation Promise Constraint Satisfaction Problems A linearly ordered (LO) k-colouring of a hypergraph assigns to each vertex a colour from the set {0,1,…,k-1} in such a way that each hyperedge has a unique maximum element. Barto, Batistelli, and Berg conjectured that it is NP-hard to find an LO k-colouring of an LO 2-colourable 3-uniform hypergraph for any constant k ≥ 2 [STACS'21] but even the case k = 3 is still open. Nakajima and Živný gave polynomial-time algorithms for finding, given an LO 2-colourable 3-uniform hypergraph, an LO colouring with O^*(√n) colours [ICALP'22] and an LO colouring with O^*(n^(1/3)) colours [ACM ToCT'23]. Very recently, Louis, Newman, and Ray gave an SDP-based algorithm with O^*(n^(1/5)) colours. We present two simple polynomial-time algorithms that find an LO colouring with O(log₂(n)) colours, which is an exponential improvement. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Johan Håstad and Björn Martinsson and Tamio-Vesa Nakajima and Stanislav Živný 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.7 urn:nbn:de:0030-drops-210006 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode