A Near-Optimal Kernel for a Coloring Problem
Ishay Haviv, Dror Rabinovich · 2025
Read A Near-Optimal Kernel for a Coloring Problem by Ishay Haviv, Dror Rabinovich (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-12281.txt.
Introduction
Ishay Haviv and Dror Rabinovich trim a coloring ask to near its floor in a 2025 paper. The ask: can a web's dots be painted in q hues with no edge joining twins. Past work tied its shrunk core size to the web's cover count, with a like-sized floor that none could pass.
A fresh cut counts the dots whose loss leaves lone edges and lone dots, a weaker trait. For that trait, they build a core near the floor, and show none can beat it by much. Shrunk cores now fit more web shapes.
Catalog record
| CREATOR | Ishay Haviv, Dror Rabinovich |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-12281
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Near-Optimal Kernel for a Coloring Problem Ishay Haviv, Dror Rabinovich Abstract For a fixed integer q q , the q -Coloring q\textsc{-Coloring} problem asks to decide if a given graph has a vertex coloring with q q colors such that no two adjacent vertices receive the same color. In a series of papers, it has been shown that for every q ≥ 3 q\geq 3 , the q -Coloring q\textsc{-Coloring} problem parameterized by the vertex cover number k k admits a kernel of bit-size O ~ ( k q − 1 ) \widetilde{O}(k^{q-1}) , but admits no kernel of bit-size O ( k q − 1 − ε ) O(k^{q-1-\varepsilon}) for ε > 0 \varepsilon>0 unless 𝖭𝖯 ⊆ 𝖼𝗈𝖭𝖯 / 𝗉𝗈𝗅𝗒 \mathsf{NP}\subseteq\mathsf{coNP/poly} (Jansen and Kratsch, 2013; Jansen and Pieterse, 2019). In 2020, Schalken proposed the question of the kernelizability of the q -Coloring q\textsc{-Coloring} problem parameterized by the number k k of vertices whose removal results in a disjoint union of edges and isolated vertices. He proved that for every q ≥ 3 q\geq 3 , the problem admits a kernel of bit-size O ~ ( k 2 q − 2 ) \widetilde{O}(k^{2q-2}) , but admits no kernel of bit-size O ( k 2 q − 3 − ε ) O(k^{2q-3-\varepsilon}) for ε > 0 \varepsilon>0 unless 𝖭𝖯 ⊆ 𝖼𝗈𝖭𝖯 / 𝗉𝗈𝗅𝗒 \mathsf{NP}\subseteq\mathsf{coNP/poly} . He further proved that for q ∈ { 3 , 4 } q\in\{3,4\} the problem admits a near-optimal kernel of bit-size O ~ ( k 2 q − 3 ) \widetilde{O}(k^{2q-3}) and asked whether such a kernel is achievable for all integers q ≥ 3 q\geq 3 . In this short paper, we settle this question in the affirmative. 1 Introduction Graph coloring is a fundamental concept in graph theory that has garnered significant attention from a computational perspective. In particular, coloring problems have been thoroughly investigated within the realm of parameterized complexity, with respect to a range of parameterizations that capture diverse aspects of the instances (see, e.g., [ 1 , 3 , 4 ] ). For a fixed integer q , let q\textsc{-Coloring} denote the problem that given an input graph G asks to decide if G is q -colorable, that is, if there exists a vertex coloring of G with q colors such that no two adjacent vertices receive the same color. Such a coloring is called a proper q -coloring of G . It is well known that the q\textsc{-Coloring} problem is solvable in polynomial time for q\in\{1,2\} and is \mathsf{NP} -complete for every q\geq 3 . The present paper focuses on structural parameterizations of the problem that are characterized by the distance of the input graph from a prescribed graph family {\cal G} . Specifically, borrowing a terminology of Cai [ 1 ] , we consider the q\textsc{-Coloring} problem on {\cal G}+k\mathrm{v} graphs, defined as follows. Input: A graph G=(V,E) and a set X\subseteq V such that G\setminus X\in{\cal G} . Question: Is G q -colorable? Parameter: The size k=|X| of the set X . Note that G\setminus X stands for the graph obtained from G by removing the vertices of X . A primary theme in parameterized complexity is kernelization, also known as data reduction, where the objective is to efficiently transform a given instance of a parameterized problem into an equivalent instance, whose size is bounded in terms of the involved parameter (see, e.g., [ 5 ] ). Formally, a kernel for a parameterized problem Q\subseteq\{0,1\}^{*}\times\mathbb{N} is an algorithm that given an instance (x,k) , where k is the parameter, runs in time polynomial in |x|+k and returns an instance (x^{\prime},k^{\prime}) , such that (x,k)\in Q if and only if (x^{\prime},k^{\prime})\in Q , with |x^{\prime}|+k^{\prime}\leq f(k) for some computable function f . The function f is referred to as the bit-size of the kernel. The kernelizability of the q\textsc{-Coloring} problems on {\cal G}+k\mathrm{v} graphs was systematically studied in 2013 by Jansen and Kratsch [ 8 ] , who provided a hierarchical classification of graph families {\cal G} according to whether the problems admit a kernel and whether the kernel is of polynomial size (see also [ 7 , Chapter 7] ). In particular, for the family Empty of edgeless graphs, which corresponds to the well-studied parameterization by the vertex cover number, they proved that for every q\geq 3 , the q\textsc{-Coloring} problem on \textsc{Empty}+k\mathrm{v} graphs admits a kernel with O(k^{q}) vertices and bit-size O(k^{q}) . This result was improved in 2019 by Jansen and Pieterse [ 9 ] , who proved that the problem admits a kernel with O(k^{q-1}) vertices and bit-size O(k^{q-1}\cdot\log k) . On the other hand, it was shown in [ 8 , 9 ] that for every integer q\geq 3 and for any \varepsilon>0 , there is no kernel for the q\textsc{-Coloring} problem on \textsc{Empty}+k\mathrm{v} graphs with bit-size O(k^{q-1-\varepsilon}) unless \mathsf{NP}\subseteq\mathsf{coNP/poly} . Since this containment would imply the unlikely collapse of the polynomial-time hierarchy [ 13 ] , these results resolve the kernelization complexity of the q\textsc{-Coloring} problem on \textsc{Empty}+k\mathrm{v} graphs up to a k^{o(1)} multiplicative term for all integers q\geq 3 . In 2020, Schalken [ 12 ] investigated the kernelizability of the q\textsc{-Coloring} problems with respect to parameters that are bounded above by the vertex cover number. Specifically, he considered the q\textsc{-Coloring} problems on \textsc{Independent Edge}+k\mathrm{v} graphs, where Independent Edge denotes the family of all graphs that form a disjoint union of edges and isolated vertices or, equivalently, the graphs whose maximum degree does not exceed 1 . It was proved in [ 12 ] that for every integer q\geq 3 , the q\textsc{-Coloring} problem on \textsc{Independent Edge}+k\mathrm{v} graphs admits a kernel with O(k^{2q-2}) vertices and bit-size O(k^{2q-2}) , whereas for any \varepsilon>0 , it admits no kernel of bit-size O(k^{2q-3-\varepsilon}) unless \mathsf{NP}\subseteq\mathsf{coNP/poly} . While these results leave a multiplicative gap of roughly k between the upper and lower bounds, it was further shown in [ 12 ] that for q\in\{3,4\} , the problem admits a kernel with O(k^{2q-3}) vertices and bit-size O(k^{2q-3}\cdot\log k) . The question of whether such a kernel exists for integers q\geq 5 was left open in [ 12 ] . The present paper resolves this question affirmatively, thereby providing a near-optimal kernel for the q\textsc{-Coloring} problem on \textsc{Independent Edge}+k\mathrm{v} graphs for all integers q\geq 3 , as stated below. Theorem 1.1 . For every integer q\geq 3 , the q\textsc{-Coloring} problem on \textsc{Independent Edge}+k\mathrm{v} graphs admits a kernel with O(k^{2q-3}) vertices and bit-size O(k^{2q-3}\cdot\log k) . The proof of Theorem 1.1 employs a powerful sparsification technique that was introduced by Jansen and Pieterse [ 10 ] for kernels of constraint satisfaction problems and found various applications since (see, e.g., [ 2 , 6 , 9 , 11 ] ). In a nutshell, their method involves expressing combinatorial constraints associated with a given instance as polynomials equated to zero and reducing the number of constraints by considering only a subset of these polynomials, which linearly spans all the others. The smaller the degree of the polynomials used, the smaller the resulting kernel size is. Based on this machinery, it was shown in [ 12 ] that in