A logarithmic approximation of linearly-ordered colourings

Conference item

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.

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

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl
• Host title: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
• Pages: 7:1-7:6
• Series: Leibniz International Proceedings in Informatics (LIPIcs)
• Series number: 317
• Publication date: 2024-09-16
• Acceptance date: 2024-07-01
• Event title: 27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024)
• Event location: London School of Economics, London, UK
• Event website: https://approxconference.com/
• Event start date: 2024-08-28
• Event end date: 2024-08-30
• DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.7
• ISSN: 1868-8969
• ISBN: 978-3-95977-348-5
• Language: English
• Keywords: hypergraph; promise constraint satisfaction problems; approximation; linear ordered colouring