Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings

Marcin Wrochna; Stanislav \v{Z}ivn\'y; Tamio-Vesa Nakajima; Zephyr Verwimp

arxiv: 2501.12062 · v3 · submitted 2025-01-21 · 💻 cs.DM · cs.CC· math.CO

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings

Tamio-Vesa Nakajima , Zephyr Verwimp , Marcin Wrochna , Stanislav \v{Z}ivn\'y This is my paper

Pith reviewed 2026-05-23 05:32 UTC · model grok-4.3

classification 💻 cs.DM cs.CCmath.CO

keywords hypergraph colouringconflict-free colouringlinearly-ordered colouringpromise CSPNP-hardnessapproximate colouringuniform hypergraphs

0 comments

The pith

Finding an ℓ-colouring of a k-colourable r-uniform hypergraph is NP-hard for most constants k, ℓ, r in three colouring variants.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper uses the algebraic approach to promise constraint satisfaction problems to classify the computational complexity of approximate colourings for hypergraphs. It proves that the problem of finding an ℓ-colouring given that a k-colouring exists is NP-hard for the standard nonmonochromatic colouring whenever 2 ≤ k ≤ ℓ and r ≥ 3. For conflict-free colourings the same hardness holds except when the hypergraph is 4-uniform and k=2, a case that is solvable in polynomial time. Linearly-ordered colourings are NP-hard to approximate for 3 ≤ k ≤ ℓ and r ≥ 4. This also yields a shorter proof of a prior result on nonmonochromatic colourings.

Core claim

What carries the argument

the algebraic approach to promise constraint satisfaction problems applied to the three hypergraph colouring variants

If this is right

It is NP-hard to find ℓ-colourings of k-colourable r-uniform hypergraphs for nonmonochromatic colouring when 2≤k≤ℓ and r≥3.
Conflict-free colouring is NP-hard to approximate except for the case r=4, k=2 which is in P.
Linearly-ordered colouring is NP-hard to approximate for 3≤k≤ℓ and r≥4.
The results give a shorter proof of the celebrated result by Dinur et al. on nonmonochromatic hypergraph colouring.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The exception for conflict-free colouring on 4-uniform hypergraphs with k=2 may connect to open problems in graph colouring.
Algebraic methods could potentially classify other promise problems in hypergraph theory.
These hardness results suggest that increasing the number of colours does not make the problems tractable in most regimes.

Load-bearing premise

The algebraic approach to promise constraint satisfaction problems applies directly to establish the complexity classifications for these hypergraph colouring variants.

What would settle it

A polynomial-time algorithm for finding an ℓ-colouring of a k-colourable r-uniform hypergraph in one of the cases claimed to be NP-hard, such as for conflict-free colouring with r=5 and k=3.

read the original abstract

Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmonochromatic colourings, conflict-free colourings, and linearly-ordered colourings. Firstly, we show that finding an $\ell$-colouring of a $k$-colourable $r$-uniform hypergraph is NP-hard for all constant $2\leq k\leq \ell$ and $r\geq 3$. This provides a shorter proof of a celebrated result by Dinur et al. [FOCS'02/Combinatorica'05]. Secondly, we show that finding an $\ell$-conflict-free colouring of an $r$-uniform hypergraph that admits a $k$-conflict-free colouring is NP-hard for all constant $3\leq k\leq\ell$ and $r\geq 4$, except for $r=4$ and $k=2$ (and any $\ell$); this case is solvable in polynomial time. The case of $r=3$ is the standard nonmonochromatic colouring, and the case of $r=2$ is the notoriously difficult open problem of approximate graph colouring. Thirdly, we show that finding an $\ell$-linearly-ordered colouring of an $r$-uniform hypergraph that admits a $k$-linearly-ordered colouring is NP-hard for all constant $3\leq k\leq\ell$ and $r\geq 4$, thus improving on the results of Nakajima and \v{Z}ivn\'y [ICALP'22/ACM TocT'23].

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper classifies complexity for three approximate hypergraph coloring variants via algebraic PCSP methods, with a shorter proof for the non-monochromatic case and mostly new hardness results for the others.

read the letter

The core result here is a set of complexity classifications for approximate nonmonochromatic, conflict-free, and linearly-ordered hypergraph colorings. Using the algebraic PCSP framework, the authors show NP-hardness for finding an ℓ-coloring of a k-colorable r-uniform hypergraph across 2 ≤ k ≤ ℓ and r ≥ 3, which shortens the Dinur et al. argument. They extend this to conflict-free colorings with hardness for 3 ≤ k ≤ ℓ and r ≥ 4 except the r=4 k=2 case, which they solve in polynomial time, and to linearly-ordered colorings with hardness in the same range for r ≥ 4. This improves on the authors' own prior ICALP work for the linearly-ordered variant and adds the conflict-free case outright. The algebraic approach is applied to the concrete templates, and the exception case indicates they verified tractability separately rather than forcing a uniform hardness claim. The citation pattern builds cleanly on established dichotomy theorems without obvious gaps. One soft spot is the need to confirm that the specific relations for conflict-free and linearly-ordered colorings do not admit overlooked polymorphisms that would collapse the hardness; the paper states the conditions hold except for the noted case, but the load-bearing step is explicit verification of the clone properties for each parameter set. If those checks are complete in the full derivations, the classifications stand. This work is aimed at researchers in hypergraph coloring and promise CSPs. A reader tracking exact complexity boundaries in combinatorial problems will find the parameter-by-parameter statements useful. It deserves peer review because the results are concrete, the method is standard in the area, and the improvements over prior proofs are measurable.

Referee Report

3 major / 2 minor

Summary. The paper uses the algebraic approach to promise constraint satisfaction problems to classify the complexity of three hypergraph colouring variants. It proves NP-hardness of finding an ℓ-colouring of a k-colourable r-uniform hypergraph for all constants 2≤k≤ℓ and r≥3, giving a shorter proof of Dinur et al. (FOCS'02/Combinatorica'05). For conflict-free colourings it establishes NP-hardness for 3≤k≤ℓ and r≥4 except the case r=4, k=2 (any ℓ), which is shown to be polynomial-time solvable. For linearly-ordered colourings it proves NP-hardness for 3≤k≤ℓ and r≥4, improving on Nakajima and Živný (ICALP'22).

Significance. If the algebraic verifications hold, the work supplies a shorter proof of an important result on approximate hypergraph colouring and extends the classification to conflict-free and linearly-ordered variants, including the identification of one new tractable case. The systematic use of PCSP polymorphism criteria is a methodological strength when the concrete templates are shown to meet the required conditions.

major comments (3)

[§3] §3 (nonmonochromatic case): the central claim that the (k,ℓ)-promise template for r-uniform hypergraphs induces a polymorphism clone without the operations needed for tractability (per the cited Barto–Kozik-type theorems) must be verified explicitly for the full range 2≤k≤ℓ, r≥3; without this check the shorter proof of Dinur et al. does not go through.
[§4.1] §4.1 (conflict-free case, r=4, k=2): the exception is load-bearing; the manuscript must exhibit the concrete polymorphism (or cite the precise theorem instance) that places this template in a tractable class, as any overlooked polymorphism would invalidate the stated polynomial-time solvability.
[§5] §5 (linearly-ordered case): the hardness statements for 3≤k≤ℓ, r≥4 rest on the claim that the corresponding promise templates satisfy the algebraic hardness criteria; the paper must confirm that no polymorphism collapses the clone into a tractable class for these parameters.

minor comments (2)

Notation for the three colouring variants should be introduced with a single consistent table or definition block early in the paper to aid comparison.
[Introduction] The abstract states the results for constant parameters; the introduction should clarify whether the proofs extend to non-constant k,ℓ,r or remain restricted to constants.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and for identifying points where the algebraic verifications can be strengthened for greater transparency. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

Referee: [§3] §3 (nonmonochromatic case): the central claim that the (k,ℓ)-promise template for r-uniform hypergraphs induces a polymorphism clone without the operations needed for tractability (per the cited Barto–Kozik-type theorems) must be verified explicitly for the full range 2≤k≤ℓ, r≥3; without this check the shorter proof of Dinur et al. does not go through.

Authors: We agree that explicit verification for the full parameter range strengthens the presentation. In the revised manuscript we will add a short subsection (or appendix) that directly checks the absence of tractability-inducing polymorphisms for the boundary cases k=2 and small values of r, confirming that the general argument applies uniformly to all 2≤k≤ℓ, r≥3. revision: yes
Referee: [§4.1] §4.1 (conflict-free case, r=4, k=2): the exception is load-bearing; the manuscript must exhibit the concrete polymorphism (or cite the precise theorem instance) that places this template in a tractable class, as any overlooked polymorphism would invalidate the stated polynomial-time solvability.

Authors: We accept that the tractability claim requires an explicit polymorphism or precise theorem citation. The revised version will state the concrete polymorphism (a binary operation satisfying the relevant tractability criterion) for the r=4, k=2 conflict-free template and name the exact theorem instance used. revision: yes
Referee: [§5] §5 (linearly-ordered case): the hardness statements for 3≤k≤ℓ, r≥4 rest on the claim that the corresponding promise templates satisfy the algebraic hardness criteria; the paper must confirm that no polymorphism collapses the clone into a tractable class for these parameters.

Authors: We will expand Section 5 with explicit arguments verifying that, for every 3≤k≤ℓ and r≥4, the polymorphism clone of the linearly-ordered promise template contains no operation that would collapse it into a tractable class according to the cited algebraic criteria. revision: yes

Circularity Check

0 steps flagged

Minor self-citation present but not load-bearing; algebraic PCSP application is independent

full rationale

The paper casts the three hypergraph colouring variants as promise CSP instances and invokes established algebraic dichotomy theorems for hardness. The sole self-citation (to Nakajima and Živný on linearly-ordered colourings) is used only to note improvement on prior results; the new hardness statements for conflict-free and linearly-ordered cases rest on the general algebraic criteria applied to the concrete templates, not on any reduction to the cited work by construction. No self-definitional steps, fitted inputs renamed as predictions, or ansatzes smuggled via citation appear. The derivation chain is therefore self-contained against external benchmarks in the algebraic PCSP literature.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based on abstract only; no free parameters or invented entities are mentioned. The central method relies on an established domain framework.

axioms (1)

domain assumption The algebraic approach to promise constraint satisfaction problems applies to hypergraph colouring variants
Explicitly stated as the method used to establish the classifications.

pith-pipeline@v0.9.0 · 5845 in / 1167 out tokens · 49436 ms · 2026-05-23T05:32:40.170633+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Equivalences of promise compactness principles
math.CO 2026-04 unverdicted novelty 8.0

For structure pairs (A,B) without Olšák polymorphisms, the promise compactness K_(A,B) is equivalent to the ultrafilter principle over ZF, including K_(K3,K5) and K_(H2,Hc).