Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings

Graph colouring is one of the most studied computational problems: Given a graph $G$ and an integer $k$, is there a $k$-colouring, i.e., an assignment of one of $k$ colours to the vertices of the graph so that adjacent vertices are assigned different colours?

Deciding the existence of a 3-colouring is one of Karp’s 21 $\mathrm{𝖭𝖯}$-complete problems [14]. Since finding a graph colouring with the smallest number of colours is $\mathrm{𝖭𝖯}$-hard, there has been much interest in the approximate graph colouring (AGC) problem: Given a graph $G$ that admits a colouring with $k$ colours, find a colouring with $\mathrm{\ell }$ colours for some $k\le \mathrm{\ell }$. It is believed that for every constant $3\le k\le \mathrm{\ell }$, this problem remains $\mathrm{𝖭𝖯}$-hard [12]. While some conditional results are known (i.e. AGC is $\mathrm{𝖭𝖯}$-hard if we assume the $d$-to-1 conjecture with perfect completeness [13]), proving unconditional results seems elusive. The strongest results known so far are for $\mathrm{\ell }=2k-1$ [4] and $\mathrm{\ell }=\left(\genfrac{}{}{0pt}{}{k}{\lfloor k/2\rfloor }\right)-1$ [15] (the first result is stronger for $k=3,4$, and equal to the second for $k=5$). As progress on proving the hardness of AGC seems to have hit a barrier, it is natural to try to attack variants of AGC, to see if any of the ideas and insights from those problems could apply to the AGC. In this paper, we will focus on hypergraph generalisations of graph colourings.

Recall that a hypergraph is a pair $(V,E)$, where $V$ is the vertex set and $E\subseteq 2^V$ the edge set. A hypergraph is called $r$-uniform if all the edges have size $r$. Thus, a 2-uniform hypergraph is a graph. A colouring of a graph $(V,E)$ is an assignment of colours $c(v)$ to the vertices $v\in V$ such that for every edge $\{u,v\}\in E$ we have $c(u)\ne c(v)$. Put differently in three different but equivalent ways, for every edge $\{u,v\}\in E$ we have that (i) the set $\{c(u),c(v)\}$ contains at least 2 elements, or (ii) some colour in the multiset $\{\{c(u),c(v)\}\}$ appears exactly once, or (iii) the largest colour in the multiset $\{\{c(u),c(v)\}\}$ appears exactly once.¹¹1This notion assumes that the colours are taken from a totally ordered set, e.g., the natural numbers. When these three definitions are applied to hypergraphs, we get three different notions, namely nonmonochromatic (NAE) colourings, conflict-free (CF) colourings, and linearly-ordered (LO) colourings. Note that any LO colouring is a CF colouring, and any CF colouring is an NAE colouring. The three notions of colourings are different already for 4-uniform²²2For 3-uniform hypergraphs, NAE and CF colourings coincide, but LO colourings are different. hypergraphs.³³3Indeed, the edge $\{a,b,c,d\}$ could be assigned colours $\{\{1,1,2,2\}\}$ in an NAE colouring, but not in the other two; whereas the edge could be assigned colours $\{\{1,2,2,2\}\}$ in a CF colouring, but not in an LO colouring.

We will now review the most relevant literature on the three variants of hypergraph colourings. It will be convenient to present the existing results in the framework of so-called promise constraint satisfaction problems (PCSPs) [6], as we shall use the tools developed for understanding the computational complexity of PCSPs [4]. Constraint satisfaction problems (CSPs) are problems that can be cast as homomorphisms between relational structures. We will only need a special case of relational structures that contain only one relation. Formally, a relational structure $𝐀=(A,R^{𝐀})$ is a pair, where $A$ is the universe of $𝐀$ and $R^{𝐀}\subseteq A^r$ is an $r$-ary relation. By abuse of language, we call $r$ the arity of $𝐀$.

An example of a relational structure is a graph or an $r$-uniform hypergraph, where the universe is the vertex set and the relation is the edge set – the arity of the relation is 2 for graphs and $r$ for $r$-uniform hypergraphs. A homomorphism from one relational structure of arity $r$, say $𝐀=(A,R^{𝐀})$, to another of the same arity, say $𝐁=(B,R^{𝐁})$, is a map $h:A\to B$ that preserves the relation: if $(a_1,\mathrm{\dots },a_r)\in R^{𝐀}$ then $(h(a_1),\mathrm{\dots },h(a_r))\in R^{𝐁}$. We denote the existence of a homomorphism from $𝐀$ to $𝐁$ by writing $𝐀\to 𝐁$.

Given two relational structures $𝐀$ and $𝐁$ with $𝐀\to 𝐁$, the promise constraint satisfaction problem with template $(𝐀,𝐁)$, denoted by $\mathrm{PCSP}(𝐀,𝐁)$, is the following computational problem. Given a relational structure $𝐗$ with $𝐗\to 𝐀$, find a homomorphism from $𝐗$ to $𝐁$. This is the search version of the problem. In the decision version, which reduces to the search version, one is given a relational structure $𝐗$ with the same arity as $𝐀$ and the task is to output Yes if $𝐗\to 𝐀$ and No if $X\to ̸𝐁$.⁴⁴4Since the decision version reduces to the search version, solving the decision version is no harder than solving the search version. All of our results will hold for both versions – hardness results will hold even for the decision version, and tractability results will hold even for the search version.

In order to cast approximate hypergraph NAE/CF/LO-colourings as PCSPs, we will need to encode the NAE/CF/LO-colourability of a hypergraph by a homomorphism to a suitable relational structure. We will thus describe three families of relational structures capturing the three types of hypergraph colourings mentioned above (and therefore implicitly graph colouring). For any arity $r\ge 2$ and domain size $k$, we define:⁵⁵5For any integer $k$, we write $[k]$ for the set $\{1,2,\mathrm{\dots },k\}$.

Observe that an $r$-uniform hypergraph $𝐗$ has an NAE $k$-colouring if and only if $𝐗\to {\mathrm{𝐍𝐀𝐄}}_k^r$. The analogous statement holds for CF and LO colourings. Since NAE, LO and CF colourings are all identical to graph colouring on uniformity 2, we see that $k$ vs. $\mathrm{\ell }$ AGC is the same as $\mathrm{PCSP}({\mathrm{𝐍𝐀𝐄}}_k^2,{\mathrm{𝐍𝐀𝐄}}_{\mathrm{\ell }}^2)$ – or equivalently $\mathrm{PCSP}({\mathrm{𝐂𝐅}}_k^2,{\mathrm{𝐂𝐅}}_{\mathrm{\ell }}^2)$ or $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_k^2,{\mathrm{𝐋𝐎}}_{\mathrm{\ell }}^2)$.

The most studied hypergraph colourings are nonmonochromatic colourings, also known as weak hypergraph colourings. This is the weakest non-trivial restriction one can impose when colouring the vertices of a hypergraph, i.e., any type of hypergraph colouring (that excludes constant colourings) is also a nonmonochromatic colouring. As mentioned before, nonmonochromatic $k$-colourings of an $r$-uniform hypergraph correspond to homomorphisms from the hypergraph to ${\mathrm{𝐍𝐀𝐄}}_k^r$. Since nonmonochromatic colouring is $\mathrm{𝖭𝖯}$-hard for any uniformity $r\ge 3$ and number of colours $k\ge 2$, Dinur, Regev, and Smith investigated the approximate version, establishing the following result [9].

In this paper we will show a simpler proof of this result. The proof in [9] relies on constructing a somewhat ad-hoc reduction and analysing its completeness and soundness. We recast this proof in the recent algebraic framework for PCSPs [4]. We also replace the use of Schrijver graphs with the simpler Kneser graphs, plus a (correct and very easy) case of Hedetniemi’s conjecture (cf. Lemma 9). We believe that our simplification is of interest since it replaces a more quantitative analysis of the polymorphisms with one that only deals with constants everywhere. In particular, this means that our proof does not require the full strength of the PCP theorem – only the “baby PCP” of Barto and Kozik [5].

A conflict-free hypergraph colouring is a colouring of the vertices in a hypergraph such that every hyperedge has at least one uniquely coloured vertex [10, 18]. As mentioned before, conflict-free $k$-colourings of an $r$-uniform hypergraph correspond to homomorphisms from the hypergraph to ${\mathrm{𝐂𝐅}}_k^r$. We shall determine the complexity of $\mathrm{PCSP}({\mathrm{𝐂𝐅}}_k^r,{\mathrm{𝐂𝐅}}_{\mathrm{\ell }}^r)$ for all constants $2\le k\le \mathrm{\ell }$ and $r\ge 3$ (the case of $r=3$ corresponding to nonmonochromatic colourings, i.e., ${\mathrm{𝐂𝐅}}_k^3={\mathrm{𝐍𝐀𝐄}}_k^3$ for every $k$).

After the easy observation that $\mathrm{PCSP}({\mathrm{𝐂𝐅}}_k^r,{\mathrm{𝐂𝐅}}_{\mathrm{\ell }}^r)$ reduces to $\mathrm{PCSP}({\mathrm{𝐂𝐅}}_k^{r+t},{\mathrm{𝐂𝐅}}_{\mathrm{\ell }}^{r+t})$ for $t\ge 2$ (cf. Lemma 6 in Section 2), Theorem 1 directly implies $\mathrm{𝖭𝖯}$-hardness for promise conflict-free colouring for uniformity $r\ge 5$. The crux of the result is to deal with the case of uniformity $r=4$. Note that finding a conflict-free colouring of a 4-uniform hypergraph using 2 colours is identical to solving systems of equations of the form $x+y+z+t\equiv 1(mod2)$ over ${\mathbb{Z}}_2$, and is hence in $𝖯$ and consequently so is $\mathrm{PCSP}({\mathrm{𝐂𝐅}}_2^4,{\mathrm{𝐂𝐅}}_{\mathrm{\ell }}^4)$ for every $\mathrm{\ell }\ge 2$. We resolve the only remaining case, showing in Section 3.3 that $\mathrm{PCSP}({\mathrm{𝐂𝐅}}_k^4,{\mathrm{𝐂𝐅}}_{\mathrm{\ell }}^4)$ is $\mathrm{𝖭𝖯}$-hard for all $3\le k\le \mathrm{\ell }$. Summarising, we have

This also immediately implies the following (much weaker) corollary, which does not appear to have been known in the CF-colouring literature.

A linearly-ordered [3] (or unique-maximum [8]) hypergraph colouring is a colouring of the vertices in a hypergraph with linearly-ordered colours such that the maximum colour in every hyperedge is unique. As mentioned before, linearly-ordered $k$-colourings of an $r$-uniform hypergraph correspond to homomorphisms from the hypergraph to ${\mathrm{𝐋𝐎}}_k^r$.

Barto at al. [3] conjectured that $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_k^3,{\mathrm{𝐋𝐎}}_{\mathrm{\ell }}^3)$ is $\mathrm{𝖭𝖯}$-hard for all constant $2\le k\le \mathrm{\ell }$, but even the case $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_2^3,{\mathrm{𝐋𝐎}}_3^3)$ is still open. A recent result of Filakovský et al. [11] established $\mathrm{𝖭𝖯}$-hardness of $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_3^3,{\mathrm{𝐋𝐎}}_4^3)$ by generalising the topological methods of Krokhin et al. [15]. Nakajima and Živný [17] also showed $\mathrm{𝖭𝖯}$-hardness of $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_k^r,{\mathrm{𝐋𝐎}}_{\mathrm{\ell }}^r)$ for every $2\le k\le \mathrm{\ell }$ and $r\ge \mathrm{\ell }-k+4$. We strengthen this result, showing $\mathrm{𝖭𝖯}$-hardness of $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_k^r,{\mathrm{𝐋𝐎}}_{\mathrm{\ell }}^r)$ when $3\le k\le \mathrm{\ell }$ and $r\ge 4$.

Observe that this theorem covers nearly all the cases from the result of [17]: the only case not covered is $k=2$ and $r\ge \mathrm{\ell }+2$. In particular, Theorem 4 has no requirement on $r$ in terms of $\mathrm{\ell }$, unlike the result in [17]. Indeed, Theorem 4 covers the full range of parameters except for the cases $r=3$ or $k=2$ (and thus the conjecture of Barto et al. remains open).

It is worth digressing somewhat to discuss the appearance of topological methods within these proofs. Our proof uses the chromatic number of the Kneser graph as an essential ingredient – this is a topological fact, and thus our proof is in some sense topological. (This is similar to the appearance of topology within hardness proofs for rainbow colourings [2].) On the other hand, the topological approach of [11], which proved that $\mathrm{PCSP}({\mathrm{𝐋𝐎}}_3^3,{\mathrm{𝐋𝐎}}_4^3)$ is $\mathrm{𝖭𝖯}$-hard, is rather different. It assigns each relational structure an equivariant simplicial complex in a “nice enough” way so that the topological properties of these simplicial complexes imply the hardness of the original template. It would be interesting to see if these two approaches can be merged, or combined to strengthen both.