A logarithmic approximation of linearly-ordered colourings

Journal article

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^*(\sqrt{n})$ colours (ICALP’22) and an LO colouring with $O^*\sqrt[3]{n}$ colours (ToCT 2023). Very recently, Louis, Newman, and Ray gave an SDP-based algorithm with $O^*\sqrt[5]{n}$ colours (FSTTCS’24). We present two simple polynomial-time algorithms that find an LO colouring with $O(\log_2(n))$ colours, which is an exponential improvement.

Authors: Håstad, J; Martinsson, B; Nakajima, T-V; Zivny, S

• Publication status: Accepted
• Peer review status: Peer reviewed
• Publisher: Department of Computer Science, University of Chicago
• Journal: Theory of Computing
• Acceptance date: 2025-06-11
• ISSN: 1557-2862
• Language: English
• Keywords: promise constraint satisfaction problems; linear ordered colouring; hypergraph; approximation