pith. sign in

arxiv: 2604.21531 · v1 · submitted 2026-04-23 · 💻 cs.CC · cs.DS

Kernelization Bounds for Constrained Coloring

Ishay Haviv This is my paper

Pith reviewed 2026-05-08 13:04 UTC · model grok-4.3

classification 💻 cs.CC cs.DS
keywords kernelizationconstraint satisfactioncoloring problemsrainbow coloringparameterized algorithmscoNP/polyhypergraph coloringgraph kernels
0
0 comments X

The pith

The infimum kernel size exponent for uniformly rainbow-free coloring is determined for all d, ℓ, q under the assumption NP not in coNP/poly.

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

This paper determines the precise polynomial degree for kernels in a family of constrained coloring problems. It first derives a general conditional lower bound for CSPs consisting of non-equality and one additional permutation-invariant relation, with the bound depending on the largest arity of any OR relation that can be defined from the extra relation. The authors then apply this to uniformly rainbow-free q-coloring, computing the exact infimum η for every admissible d, ℓ, and q. A sympathetic reader cares because these bounds classify which coloring problems admit small polynomial kernels and which require larger ones, resolving several open questions on kernel complexity for graphs and hypergraphs under natural parameterizations.

Core claim

We determine, for all admissible values of d, ℓ, and q, the infimum over all values η for which the uniformly rainbow free coloring problem admits a kernel of size O(n^η), under the assumption NP ⊈ coNP/poly. The determination follows from establishing a conditional lower bound on kernel size in terms of the largest arity of an OR relation definable from the additional relation R in the corresponding CSP.

What carries the argument

The largest arity of an OR relation definable from the permutation-invariant relation R, which controls the kernel lower bound for the associated CSP with non-equality constraints.

Load-bearing premise

That NP is not contained in coNP/poly, and that the lower bound construction applies whenever the largest arity of definable OR relations is fixed.

What would settle it

Discovering a kernel of size O(n^η') with η' strictly less than the determined infimum for some specific d, ℓ, q, which would contradict the lower bound unless the complexity assumption fails.

Figures

Figures reproduced from arXiv: 2604.21531 by Ishay Haviv.

Figure 1
Figure 1. Figure 1: The gadgets used in Lemma 3.3 to prevent assigning the colors view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of the proof of Lemma 4.2 for view at source ↗
read the original abstract

We study the kernel complexity of constraint satisfaction problems over a finite domain, parameterized by the number of variables, whose constraint language consists of two relations: the non-equality relation and an additional permutation-invariant relation $R$. We establish a conditional lower bound on the kernel size in terms of the largest arity of an OR relation definable from $R$. Building on this, we investigate the kernel complexity of uniformly rainbow free coloring problems. In these problems, for fixed positive integers $d$, $\ell$, and $q \geq d$, we are given a graph $G$ on $n$ vertices and a collection $\cal F$ of $\ell$-tuples of $d$-subsets of its vertex set, and the goal is to decide whether there exists a proper coloring of $G$ with $q$ colors such that no $\ell$-tuple in $\cal F$ is uniformly rainbow, that is, no tuple has all its sets colored with the same $d$ distinct colors. We determine, for all admissible values of $d$, $\ell$, and $q$, the infimum over all values $\eta$ for which the problem admits a kernel of size $O(n^\eta)$, under the assumption $\mathsf{NP} \nsubseteq \mathsf{coNP/poly}$. As applications, we obtain nearly tight bounds on the kernel complexity of various coloring problems under diverse settings and parameterizations. This includes graph coloring problems parameterized by the vertex-deletion distance to a disjoint union of cliques, resolving a question of Schalken (2020), as well as uniform hypergraph coloring problems parameterized by the number of vertices, extending results of Jansen and Pieterse (2019) and Beukers (2021).

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.

Referee Report

2 major / 2 minor

Summary. The manuscript studies kernelization for CSPs consisting of the non-equality relation together with one additional permutation-invariant relation R. It derives conditional lower bounds on kernel size in terms of the maximum arity of an OR relation definable from R. It then specializes to the uniformly rainbow-free coloring problem: given a graph G on n vertices and a collection F of ℓ-tuples of d-subsets, decide whether G admits a proper q-coloring in which no tuple in F is uniformly rainbow. For every admissible triple (d, ℓ, q) with q ≥ d the paper determines the exact infimum η such that the problem admits an O(n^η) kernel, assuming NP ⊈ coNP/poly. Applications include graph coloring parameterized by vertex-deletion distance to a disjoint union of cliques and uniform hypergraph coloring parameterized by number of vertices.

Significance. If the lower-bound constructions are correct, the work supplies a complete, nearly tight classification of kernel exponents for this family of constrained coloring problems. It resolves the open question of Schalken (2020) on deletion-to-clique-union parameterization and extends the hypergraph-coloring kernel results of Jansen & Pieterse (2019) and Beukers (2021). The reduction strategy via definable OR relations under the standard coNP/poly assumption is a methodological strength.

major comments (2)
  1. [§3] §3 (lower-bound construction): the claim that the largest arity of any OR relation definable from R is a constant depending only on the fixed parameters d, ℓ, q must be verified explicitly for the rainbow-free encoding; if the arity grows with n in any admissible case, the stated η would be incorrect.
  2. [Theorem 5.3] Theorem 5.3 (main classification): the proof that every admissible (d, ℓ, q) falls into one of the enumerated exponent cases relies on exhaustive case analysis of definable OR arities; the manuscript should supply a short table or lemma that lists, for each (d, ℓ, q), the computed maximum arity and the resulting η.
minor comments (2)
  1. [Abstract] The abstract uses 'admissible values' of d, ℓ, q without definition; a one-sentence clarification of the constraints (e.g., ℓ ≥ 1, q ≥ d ≥ 1) would improve readability.
  2. [§4] Notation for the collection F of ℓ-tuples of d-subsets is introduced without a small concrete example; adding one would help readers follow the uniform-rainbow condition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and constructive suggestions. We address the two major comments point by point below.

read point-by-point responses

  1. Referee: [§3] §3 (lower-bound construction): the claim that the largest arity of any OR relation definable from R is a constant depending only on the fixed parameters d, ℓ, q must be verified explicitly for the rainbow-free encoding; if the arity grows with n in any admissible case, the stated η would be incorrect.

    Authors: We agree that an explicit verification is useful. In the uniformly rainbow-free coloring encoding, the relation R is defined directly from the fixed parameters d, ℓ, and q (see the formal definition in Section 3). The domain has fixed size q, and R is permutation-invariant. Consequently, only finitely many relations are definable from R, so the maximum arity of any definable OR relation is bounded by a constant that depends solely on d, ℓ, q and is independent of the input size n. We will insert a short remark or auxiliary lemma in §3 that states this fact explicitly and confirms that the arity remains constant across all admissible instances. revision: yes

  2. Referee: [Theorem 5.3] Theorem 5.3 (main classification): the proof that every admissible (d, ℓ, q) falls into one of the enumerated exponent cases relies on exhaustive case analysis of definable OR arities; the manuscript should supply a short table or lemma that lists, for each (d, ℓ, q), the computed maximum arity and the resulting η.

    Authors: We thank the referee for this readability suggestion. The exhaustive case analysis already appears in the proof of Theorem 5.3, but a compact summary will make the classification easier to consult. We will add a table (or a short lemma) immediately before Theorem 5.3 that enumerates every admissible triple (d, ℓ, q), records the maximum arity of an OR relation definable from the corresponding R, and states the resulting kernel exponent η. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives conditional kernel-size lower bounds for rainbow-free coloring and related CSPs by standard polynomial-time reductions from known hard problems (under the external assumption NP ⊈ coNP/poly). The central parameter η is obtained from the maximum arity of an OR relation definable from the fixed permutation-invariant relation R; this arity is a constant for each admissible (d, ℓ, q) triple and does not depend on the target kernel exponent. No equation equates a derived quantity to a fitted input, no uniqueness theorem is imported from the authors' prior work, and no ansatz is smuggled via self-citation. The argument is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard complexity assumption NP ⊈ coNP/poly and on the definition of OR relations definable from the given constraint language; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption NP is not contained in coNP/poly
    Used to derive conditional lower bounds on kernel size.

pith-pipeline@v0.9.0 · 5608 in / 1153 out tokens · 74362 ms · 2026-05-08T13:04:18.539032+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances

    cs.DM 2026-05 unverdicted novelty 7.0

    Authors reframe gadget reductions for CSP non-redundancy using hypergraph projections and shrinking factors to obtain improved super-linear lower bounds for select predicates, with SAT solvers used to discover reducti...

Reference graph

Works this paper leans on

27 extracted references · 2 canonical work pages · cited by 1 Pith paper

  1. [1]

    Berkman and I

    Y. Berkman and I. Haviv. Kernelization forH-coloring. InProc. of the 20th International Sym- posium on Parameterized and Exact Computation (IPEC’25), pages 5:1–17, 2025

    2025

  2. [2]

    Bessiere, C

    C. Bessiere, C. Carbonnel, and G. Katsirelos. Chain length and CSPs learnable with few queries. InProc. of the 34th AAAI Conference on Artificial Intelligence (AAAI’20), pages 1420– 1427, 2020

    2020

  3. [3]

    S. Beukers. Extending the scope of algebraic kernelization for constraint satisfaction prob- lems. M.Sc. Thesis, Technische Universiteit Eindhoven, 2021

    2021

  4. [4]

    Brakensiek and V

    J. Brakensiek and V . Guruswami. Redundancy is all you need. InProc. of the 57th Annual ACM Symposium on Theory of Computing (STOC’25), pages 1614–1625, 2025

    2025

  5. [5]

    Brakensiek, V

    J. Brakensiek, V . Guruswami, B. M. P . Jansen, V . Lagerkvist, and M. Wahlström. The richness of CSP non-redundancy.arXiv, abs/2507.07942, 2025

    work page arXiv 2025

  6. [6]

    A. A. Bulatov. A dichotomy theorem for nonuniform CSPs. InProc. of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS’17), pages 319–330, 2017

    2017

  7. [7]

    L. Cai. Parameterized complexity of vertex colouring.Discret. Appl. Math., 127(3):415–429, 2003

    2003

  8. [8]

    Carbonnel

    C. Carbonnel. On redundancy in constraint satisfaction problems. InProc. of the 28th Inter- national Conference on Principles and Practice of Constraint Programming (CP’22), pages 11:1–15, 2022

    2022

  9. [9]

    H. Chen, B. M. P . Jansen, K. Okrasa, A. Pieterse, and P . Rz ˛ a ˙zewski. Sparsification lower bounds for listH-coloring.ACM Trans. Comput. Theory, 15(3–4):8:1–23, 2023. Preliminary version in ISAAC’20

    2023

  10. [10]

    H. Chen, B. M. P . Jansen, and A. Pieterse. Best-case and worst-case sparsifiability of Boolean CSPs.Algorithmica, 82(8):2200–2242, 2020. Preliminary version in IPEC’18

    2020

  11. [11]

    Dell and D

    H. Dell and D. van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses.J. ACM, 61(4):23:1–27, 2014. Preliminary version in STOC’10

    2014

  12. [12]

    P . Erd˝ os. On extremal problems of graphs and generalized graphs.Israel J. Math., 2(3):183– 190, 1964

    1964

  13. [13]

    F. V . Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi.Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019

    2019

  14. [14]

    Haviv and D

    I. Haviv and D. Rabinovich. A near-optimal kernel for a coloring problem.Discret. Appl. Math., 377:66–73, 2025. 31

    2025

  15. [15]

    Haviv and D

    I. Haviv and D. Rabinovich. Kernelization for orthogonality dimension.J. Comput. Syst. Sci., 157:103757, 2026. Preliminary version in IPEC’24

    2026

  16. [16]

    B. M. P . Jansen and S. Kratsch. Data reduction for graph coloring problems.Inf. Comput., 231:70–88, 2013. Preliminary version in FCT’11

    2013

  17. [17]

    B. M. P . Jansen and A. Pieterse. Sparsification upper and lower bounds for graph problems and not-all-equal SAT.Algorithmica, 79(1):3–28, 2017. Preliminary version in IPEC’15

    2017

  18. [18]

    B. M. P . Jansen and A. Pieterse. Optimal data reduction for graph coloring using low-degree polynomials.Algorithmica, 81(10):3865–3889, 2019. Preliminary version in IPEC’17

    2019

  19. [19]

    B. M. P . Jansen and A. Pieterse. Optimal sparsification for some binary CSPs using low- degree polynomials.ACM Trans. Comput. Theory, 11(4):28:1–26, 2019. Preliminary version in MFCS’16

    2019

  20. [20]

    B. M. P . Jansen and M. Włodarczyk. Optimal polynomial-time compression for Boolean max CSP.ACM Trans. Comput. Theory, 16(1):4:1–20, 2024

    2024

  21. [21]

    Lagerkvist and M

    V . Lagerkvist and M. Wahlström. Sparsification of SAT and CSP problems via tractable ex- tensions.ACM Trans. Comput. Theory, 12(2):13:1–29, 2020. Preliminary version in CP’17

    2020

  22. [22]

    Lagerkvist and M

    V . Lagerkvist and M. Wahlström. The (coarse) fine-grained structure of NP-hard SAT and CSP problems.ACM Trans. Comput. Theory, 14(1):2:1–54, 2022

    2022

  23. [23]

    Piecyk, A

    M. Piecyk, A. Pieterse, P . Rz ˛ a˙zewski, and M. Wahlström. Kernelization for listH-coloring for graphs with small vertex cover.arXiv, abs/2507.12005, 2025

    work page arXiv 2025

  24. [24]

    T. J. Schaefer. The complexity of satisfiability problems. InProc. of the 10th Annual ACM Symposium on Theory of Computing (STOC’78), pages 216–226. ACM, 1978

    1978

  25. [25]

    M. M. R. Schalken. Efficient kernels forq-coloring. M.Sc. Thesis, Technische Universiteit Eindhoven, 2020

    2020

  26. [26]

    C. Yap. Some consequences of non-uniform conditions on uniform classes.Theor. Comput. Sci., 26(3):287–300, 1983

    1983

  27. [27]

    D. Zhuk. A proof of the CSP dichotomy conjecture.J. ACM, 67(5):30:1–78, 2020. Preliminary version in FOCS’17. 32

    2020