Kernelization for $𝑯$-Coloring

Our first kernel is simple and combinatorial, inspired by the strategy developed for coloring problems by Jansen and Kratsch in [23]. Consider an instance of the $H\text{-Coloring}$ problem parameterized by the vertex cover number $k$, namely, a graph $G=(V,E)$ and a vertex cover $X\subseteq V$ of $G$ of size $k$. For a fixed integer $q$, the kernel starts with the subgraph of $G$ induced by $X$, and then, for every set $S\subseteq X$ of size at most $q$ whose vertices share a neighbor from $V\setminus X$ in $G$, introduces a new vertex whose neighborhood is exactly $S$. While the number of vertices in the constructed graph is clearly bounded by $O(k^q)$, we prove that the correctness of the kernelization for $H\text{-Coloring}$ is governed by a structural quantity of the graph $H$, which we denote by $q(H)$ and refer to as the non-adjacency witness number of $H$.

Given a set of vertices in $H$ that have no common neighbor, one may ask whether this can be certified by a succinct witness, namely, a small subset that also has no common neighbor. The non-adjacency witness number $q(H)$ is defined as the smallest size of such a subset, whose existence is guaranteed for every set of vertices in $H$ with no common neighbor (see Definition 6). This notion has previously been studied in the literature, with particular attention given to graphs $H$ with $q(H)=2$ (see, e.g., [6, 14, 13]). We note that $q(H)$ may also be formulated as the smallest integer $q$ for which the collection of open neighborhoods in $H$ satisfies what is known as the Helly property of order $q$. Our analysis reveals that the size of the aforementioned kernel for the $H\text{-Coloring}$ problem parameterized by the vertex cover number is bounded by a polynomial, whose degree is given by the non-adjacency witness number of $H$.

We remark that when applying Theorem 1, it is sometimes useful to replace $H$ with a core subgraph of $H$. As noted earlier, this substitution does not change the problem, however, it may reduce the non-adjacency witness number and thereby lead to a smaller kernel.

In an attempt to exploit Theorem 1 and to compare it with the kernel of $O(k^{\mathrm{\Delta }(H)})$ vertices obtained in [24], we undertake a systematic study of the non-adjacency witness number of graphs. Our analysis illuminates connections to fundamental graph parameters, such as maximum degree, clique number, and degeneracy, as well as structural properties related to the presence of specific subgraphs. By combining these insights with Theorem 1, we obtain economical kernels for a broad range of graphs $H$. In particular, as demonstrated below, we achieve kernels whose size is bounded by a fixed polynomial for natural classes of graphs $H$ with unbounded maximum degree.

For a fixed integer $d$, consider the class of $d$-degenerate graphs, namely, those graphs in which every subgraph has a vertex of degree at most $d$. We show that for every such graph $H$, its non-adjacency witness number satisfies $q(H)\le d+1$, so Theorem 1 implies that the corresponding $H\text{-Coloring}$ problem parameterized by the vertex cover number $k$ admits a kernel whose size is bounded by $O(k^{d+1})$. For planar graphs, which are known to be $5$-degenerate, this yields a bound of $O(k^6)$ on the kernel size, and via a refined analysis, we further reduce it to $O(k^4)$. Perhaps most strikingly, we apply Theorem 1 to show that for almost every graph $H$, there is a kernel for the $H\text{-Coloring}$ problem parameterized by the vertex cover number, where the degree of the polynomial bounding its size grows only logarithmically with the maximum degree of $H$. To this end, we provide a tight estimate for the typical non-adjacency witness number of random graphs.

Our second kernel for the $H\text{-Coloring}$ problem parameterized by the vertex cover number is more algebraic in nature. For certain graphs $H$, it allows us to sharpen the kernel size from Theorem 1 by a multiplicative linear factor. Somewhat surprisingly, the condition that makes this improvement applicable is related to the concept of faithful orthogonal representations of graphs (which, as described earlier, assign a non-self-orthogonal vector to each vertex, such that two vertices are adjacent if and only if their vectors are orthogonal). Concretely, we show that if a graph $H$ admits a faithful $d$-dimensional orthogonal representation over some computationally efficient field, then the $H\text{-Coloring}$ problem parameterized by the vertex cover number $k$ admits a kernel with $O(k^{d-1})$ vertices and bit-size $O(k^{d-1}\cdot \log k)$.

In fact, we obtain this kernel size under a weaker assumption on the graph $H$, using the concept of independent representations of graphs. This notion refers to an assignment of a $d$-dimensional vector to each vertex of $H$, so that the vector associated with each vertex does not lie in the vector space spanned by the vectors of its neighborhood. Note that every orthogonal representation is, in particular, an independent representation. The minimum dimension of an independent representation of a graph over a given field characterizes a well-studied graph quantity, called minrank, which plays a pivotal role in the study of fundamental problems in information theory, such as Shannon capacity [15], index coding [1, 40, 16], storage capacity [33], and hat guessing games [38]. For our purposes, we introduce a faithful analogue of this notion, demanding that two vertices $u$ and $v$ in the graph are adjacent if and only if the vector associated with $u$ lies in the linear subspace spanned by the vectors of the neighborhood of $v$ (see Definition 9). With this faithful variant in hand, we prove the following theorem (see also Theorem 14).

A few remarks are in order here. First, it is not difficult to show that every graph $H$ has a faithful independent representation of dimension $\mathrm{\Delta }(H)+1$ over any sufficiently large field (see Lemma 13). By Theorem 2, this implies that for every graph $H$, the $H\text{-Coloring}$ problem parameterized by the vertex cover number $k$ admits a kernel with $O(k^{\mathrm{\Delta }(H)})$ vertices and bit-size $O(k^{\mathrm{\Delta }(H)}\cdot \log k)$. Therefore, Theorem 2 strengthens the kernel bound implied by [24]. It is worth noting that a result of Maehara and Rödl [31] asserts that every graph $H$ has a faithful orthogonal representation over $ℝ$ of dimension $2\cdot \mathrm{\Delta }(H)$, and it is an open question whether this dimension can be reduced to $\mathrm{\Delta }(H)+1$ (see, e.g., [29, Chapter 10.4]). Thus, for Theorem 2 to fully subsume the kernel bound of [24], it is somewhat crucial to adopt the more flexible notion of faithful independent representations (rather than orthogonal).

Second, we observe that for every graph $H$ that possesses a faithful $d$-dimensional independent representation over some field, the non-adjacency witness number satisfies $q(H)\le d$ (see Lemma 11). This shows that Theorem 2 improves the kernel size obtained via Theorem 1 only when the minimum dimension of a faithful independent representation of $H$ matches the non-adjacency witness number of $H$ (in fact, of a minimal core subgraph of $H$). This situation arises, for example, for the aforementioned graphs $H=H(𝔽,d)$, which correspond to the existence of a $d$-dimensional orthogonal representation over a field $𝔽$. As an application of Theorem 2, we unleash a near-optimal kernel for the $d{\text{-Ortho-Dim}}_{𝔽}$ problems over finite fields $𝔽$, thereby settling a question posed in [18].

We further demonstrate the applicability of Theorem 2 for the celebrated family of Kneser graphs. For positive integers $m$ and $r$ with $m\ge 2r$, the Kneser graph $K(m,r)$ has all $r$-subsets of an $m$-element set as vertices, where two are adjacent if they are disjoint. It turns out that the non-adjacency witness number of $K(m,r)$ is $m-2r+2$, coinciding with its chromatic number that was determined in an influential paper of Lovász [27]. By Theorem 1, this shows that the $K(m,r)$-Coloring problem parameterized by the vertex cover number $k$ admits a kernel with $O(k^{m-2r+2})$ vertices and bit-size. To further reduce this kernel size, we prove that $K(m,r)$ admits a faithful $(m-2r+2)$-dimensional independent representation over any sufficiently large field, which yields, via Theorem 2, a kernel with $O(k^{m-2r+1})$ vertices and bit-size $O(k^{m-2r+1}\cdot \log k)$. In particular, for the $3$-chromatic Kneser graphs $K(2r+1,r)$, which include the iconic Petersen graph $K(5,2)$, the resulting kernel has near-quadratic size (see Figure 1).

The proof of Theorem 2 builds on a powerful sparsification technique that was introduced by Jansen and Pieterse in [25] and applied in their work [24]. To illustrate this technique, consider an instance of the $H\text{-Coloring}$ problem parameterized by the vertex cover number, consisting of a graph $G=(V,E)$ and a vertex cover $X\subseteq V$ of $G$. The approach begins by introducing variables over some field $𝔽$ that represent an assignment of vertices from $H$ to the vertices in $X$. Then, for every vertex $v\in V\setminus X$, one constructs one or more low-degree polynomials in the variables corresponding to its neighbors in $X$, which evaluate to zero if and only if $v$ can be assigned a compatible vertex from $H$. The crux is that it suffices to retain in the graph $G$ only a subset of the vertices in $V\setminus X$, whose corresponding polynomials linearly span all the others. The degree of the used polynomials determines the dimension of the entire space of polynomials, and consequently, the resulting kernel size. This method was applied in [24], where the assignment of each vertex of $X$ is encoded by a set of variables representing an indicator vector over the binary field ${𝔽}_2$.

The way we apply the machinery of [24, 25] to prove Theorem 2 is substantially different. We rely on the existence of a faithful $d$-dimensional independent representation of the graph $H$ over some field $𝔽$, interpreting its vectors as encodings of the vertices of $H$. Accordingly, we associate each vertex in the vertex cover $X$ with a $d$-dimensional variable vector over $𝔽$ to represent its assignment. The kernelization algorithm first applies our combinatorial kernel to ensure that every vertex outside $X$ has degree at most $d$. Then, it aims to reduce the number of vertices outside $X$ that have degree exactly $d$. By the definition of an independent representation, a vertex $v$ outside $X$ can be assigned a compatible vertex from $H$ only if every set of $d$ vectors of its neighbors in $X$ is linearly dependent over $𝔽$. This condition can be naturally captured by requiring the determinant polynomial over the variables corresponding to such $d$ neighbors of $v$ to be zero. Once the vectors of the neighbors of $v$ span a subspace of dimension smaller than $d$, the assignment of a compatible vertex to $v$ is essentially realized through some other vertex outside $X$ of degree at most $d-1$.

However, the degree of the determinant polynomial of a $d\times d$ matrix is $d$. In order to obtain polynomials of degree $d-1$, which in turn yield a kernel with $O(k^{d-1})$ vertices, we use an idea from [18, 19] and require all vectors in the faithful independent representation of $H$ to share a fixed value, say $1$, in their first entry. When the field $𝔽$ is sufficiently large relative to the number of vertices in $H$, this can be achieved by applying an invertible linear transformation to the vectors in the representation to ensure that all first entries are nonzero, and then scaling them appropriately. Over a smaller field, though, such a representation may not exist. We overcome this obstacle by showing that if a graph has a faithful $d$-dimensional independent representation over some field $𝔽$, then it also has one in which all vectors have $1$ as their first entry, over any sufficiently large extension field of $𝔽$ (see Lemma 12). This allows us to apply the approach described above over such an extension field and obtain a kernel of the desired size.

Given our combinatorial and algebraic kernels for the $H\text{-Coloring}$ problem parameterized by the vertex cover number $k$, it is natural to ask how close the obtained kernel sizes come to being optimal. As already discussed, and shown in [23, 24], when $H$ is the complete graph on $q$ vertices with $q\ge 3$, the problem admits no kernel of size $O(k^{q-1-\epsilon })$ for any $\epsilon >0$, unless $\mathrm{𝖭𝖯}\subseteq \mathrm{𝖼𝗈𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$. This firmly settles the kernel complexity for all cases where $H$, or its minimal core subgraph, is a complete graph. Turning to other fundamental graphs, the first non-trivial case that arises is that of odd cycles of length at least five. For every integer $m\ge 2$, it is easy to verify that the cycle $C_{2m+1}$ on $2m+1$ vertices has non-adjacency witness number $q(C_{2m+1})=2$. Consequently, Theorem 1 yields a kernel for the $C_{2m+1}$-Coloring problem parameterized by the vertex cover number $k$ with $O(k^2)$ vertices and bit-size. Furthermore, neither Theorem 2 nor the kernel from [24] improves upon this bound. Another notable case is the family of $3$-chromatic Kneser graphs $K(2r+1,r)$, for which Theorem 2 yields a kernel with $O(k^2)$ vertices and bit-size $O(k^2\cdot \log k)$. The following theorem indicates that, in both cases, the obtained kernel sizes are nearly optimal.

We prove Theorem 4 in a stronger form in several respects. First, we show that the near-quadratic lower bound persists even when the $H$-Coloring problem is parameterized by the total number of vertices in the input graph. Since the entire vertex set of a graph trivially forms a vertex cover, this directly implies the statement above. Second, the proof encompasses not only the graphs $H$ stated in the theorem but also extends to various other graphs $H$. Specifically, the result is proved for all non-bipartite core graphs that are projective, a class that is known to cover nearly all graphs, including prominent and well-studied graph families (see, e.g., [26]). Third, as is standard in such results, the lower bound applies to the compressibility of the $H\text{-Coloring}$ problem into any target problem, not necessarily itself. Our generalized result is stated as follows.

The proof of Theorem 5 is based on a compression lower bound, due to Chen, Jansen, Okrasa, Pieterse, and Rzążewski [3], for a variant of the $H\text{-Coloring}$ problem called $\text{List-}H\text{-Coloring}$. In this variant, the input consists of a graph $G$ along with a list of allowed vertices of $H$ for each vertex of $G$, and the goal is to decide whether there exists a homomorphism from $G$ to $H$ that respects these lists. This problem generalizes the standard $H\text{-Coloring}$ problem, which corresponds to the special case where all lists are equal to the full vertex set of $H$. Feder, Hell, and Huang [7] introduced a class of geometric intersection graphs, called bi-arc graphs, and used this class to fully characterize the complexity of the $\text{List-}H\text{-Coloring}$ problem. They showed that the problem is solvable in polynomial time if $H$ is bi-arc, and $\mathrm{𝖭𝖯}$-hard otherwise. Chen et al. [3] proved that, unless $\mathrm{𝖭𝖯}\subseteq \mathrm{𝖼𝗈𝖭𝖯}/\mathrm{𝗉𝗈𝗅𝗒}$, the $\text{List-}H\text{-Coloring}$ problem parameterized by the number of vertices admits no sub-quadratic compression for any $H$ that is not bi-arc. They also posed the question of whether such a lower bound holds for the (non-list) $H\text{-Coloring}$ problem, when $H$ is loopless and non-bipartite. As a step toward this challenge, Theorem 5 confirms the lower bound for the substantial class of non-bipartite projective core graphs $H$. To this end, we show that for such graphs $H$, instances of $\text{List-}H\text{-Coloring}$ can be efficiently reduced into instances of $H\text{-Coloring}$, with the number of vertices preserved up to a multiplicative constant. The proof borrows a gadget construction due to Okrasa and Rzążewski [35] and echoes early $\mathrm{𝖭𝖯}$-hardness proofs for $H\text{-Coloring}$ problems [34, 32], as well as recent lower bounds in fine-grained complexity [35, 37].

When the $H\text{-Coloring}$ problems are parameterized by the number of vertices, they admit a trivial kernel of quadratic size. Therefore, the lower bounds implied by Theorem 5 for the vertex cover parameterization are limited to the near-quadratic regime. To surpass this barrier, we establish a lower bound on the kernel size of the $H\text{-Coloring}$ problem parameterized by the vertex cover number for all non-bipartite projective core graphs $H$ with $q(H)\ge 4$. We show that, for each such graph $H$, the degree of any polynomial that bounds the kernel size is unlikely to be smaller than the non-adjacency witness number of $H$ minus one. The precise statement and proof appear in the full version of the paper. Note that this lower bound is reasonably close to our upper bounds. Indeed, for every non-bipartite projective core graph $H$ with $q(H)\ge 4$, the upper bound given in Theorem 1 exceeds this lower bound by only a near-linear multiplicative factor. Since almost all graphs are non-bipartite projective cores, our results determine the kernel complexity of the problem up to a near-linear factor for almost every graph $H$. Furthermore, if a non-bipartite projective core graph $H$ admits a faithful independent representation of dimension $q(H)\ge 4$ over a computationally efficient field, then the kernel given in Theorem 2 essentially meets the lower bound (see also Theorem 14). As an illustrative consequence, we derive that the kernel sizes we achieve for all non-bipartite Kneser graphs are nearly tight (extending Item 2 of Theorem 4).

We begin with formal definitions of these two representation types.

We note that all vectors in an independent representation of a graph are nonzero. It can be verified that a graph has a $2$-dimensional independent representation over a field if and only if it is bipartite.

We proceed by presenting several lemmas that will be used in the analysis of the algebraic kernel. Their proofs are deferred to the full version of the paper. The first lemma shows that the dimension of any faithful independent representation of a graph forms an upper bound on its non-adjacency witness number (recall Definition 6).

The following lemma states that any faithful independent representation over a field can be transformed into one of the same dimension in which every vector starts with $1$, over any sufficiently large extension field.

We finally observe that every graph admits a faithful independent representation of dimension one greater than its maximum degree over any sufficiently large field.

We are ready to present our algebraic kernel and confirm Theorem 2. To state the result in full generality, we borrow the following terminology from [25]. A field is said to be efficient if field operations and Gaussian elimination can be performed in polynomial time in the size of a reasonable input encoding. Note that all finite fields and the real field $ℝ$ (restricted to rational numbers) are efficient.