Constraint solvers handle complicated conditions, such as "these vertices must form a cover of size at most $k$" or "these variables take exactly $N$ distinct values," in one of two ways. The first is a global constraint: one specialised piece of code that reasons over all the variables at once. The second is a decomposition: the condition is rewritten as many small clauses or linear inequalities that a general engine can process. Global constraints prune more of the search, but they say little about why they pruned. That leaves a learning solver (one that records a reusable "nogood" clause after every dead end) with nothing to generalise from. Decompositions give the learner plenty of material, but for many constraints they are provably weak or very large. When the constraint is NP-hard, even the global propagator cannot be both exact and fast.
This note proposes a middle path built on loss-less kernelization: a polynomial-time reduction that shrinks the constraint to a small core while keeping every near-optimal solution, so pruning stays sound. The proposal has two parts. While the constraint is loose, the solver propagates it globally. Once the loss-less kernel at the current search node falls below a size budget, the solver writes an exact clausal encoding of that small core into the learning solver. Each clause is guarded by a short explanation of the domain facts that justified the reduction, so the clause stays valid everywhere in the search tree. The bet is that conflict learning on the hard core pays for itself where neither the black-box kernel propagator nor a full static encoding does. The tests use the VERTEXCOVER constraint, which has a known loss-less kernel, with EDGEDOMINATINGSET as a second case.
Core Claim
Two prior lines of work are each missing half of this mechanism. Propagation via Kernelization: The Vertex Cover Constraint and On the Kernelization of Global Constraints show how to propagate VERTEXCOVER by computing a $z$-rigid crown decomposition. That reduction keeps all supports within cost slack $z$ of optimal and yields a kernel of at most $(z+2)k$ vertices. It then runs an internal witness search on that kernel. The method supplies the reduction we reuse. It also motivates the proposal for two reasons: it gives no clausal reasons to the outer solver, and it loses its advantage on dense graphs or at large slack.
Just-in-Time Hierarchical Constraint Decomposition proposes the architectural idea of decomposing a global constraint lazily inside a lazy-clause-generation solver, which is a CP solver that turns propagation steps into SAT clauses. It was developed only for the tractable ALLDIFFERENT and has no quantitative rule for when to decompose. We take its lazy-decomposition idea and replace its missing trigger with a kernel-size test. Kernel size is the measure of pruning strength proposed in Reasoning about NP-complete Constraints.
The specific new claim has three parts. First, the kernel computed under the current domains can be turned into a set of clauses, each conditioned on a minimal set of domain literals the crown reduction actually depended on. Second, emitting these clauses only when the kernel is smaller than a budget $B$ gives the learner a polynomial-size, sound encoding of exactly the intractable part. Third, learned clauses over kernel variables are reused across sibling branches, which a pruning-only explanation cannot achieve.
Circuit-complexity results constrain the design. Circuit Complexity and Decompositions of Global Constraints shows that a propagator has a polynomial CNF decomposition with full unit-propagation strength only if it has a polynomial monotone circuit. For this reason we do not aim for a static exact encoding of the whole constraint. The encoding is emitted only for a kernel whose size is bounded by a function of $k$ and $z$, and that bound is what keeps the clause count polynomial.
Research Program
The work has three technical components.
Explained crown reductions. The zCrown algorithm removes crown vertices and forces their neighbourhoods into the cover. The reasons for these steps are local: they depend on the matching between the crown and its head and on the vertices already fixed in that neighbourhood. We will derive an explanation procedure that keeps only those fixed literals. We will then measure explanation length against the naive explanation, which is "all current fixings." This component also produces the pure explaining-propagator variant used as the main ablation. It addresses the open item listed as Gap 3 in the research file, following the explanation-by-traversal style of Explaining Propagators for String Edit Distance Constraints. That work explains a dynamic-programming matrix for an NP-hard constraint. We explain a graph reduction instead.
Guarded kernel encoding. When the kernel $K$ satisfies $|K| \le B$, we emit three things: the edge clauses of $K$, a sequential-counter encoding of the remaining budget $k - |\text{forced}|$, and the crown forcings. Every clause is prefixed with the negated explanation literals. The encoding size is $O(|K| \cdot k)$, and the $(z+2)k$ bound keeps it polynomial in $k$ and $z$.
Emitted clauses are tagged so the solver's clause-deletion policy can drop them like learned clauses. This avoids the memory build-up that Just-in-Time Hierarchical Constraint Decomposition attributes to eager decomposition. We will also prove soundness, by showing the guarded clauses are implied by the original constraint, and completeness relative to the kernel.
Trigger policy. The budget $B$ is the single control knob. Above it, the solver uses the global kernel propagator together with a cheap clique bound. Below it, the solver emits the encoding once per explanation. We will study three settings: fixed $B$, $B$ proportional to the current number of learned clauses, and never emitting when $z$ is large relative to $k$. The last setting is where the $(z+2)k$ kernel approaches the full graph.
The second constraint, EDGEDOMINATINGSET, has an $\infty$-loss-less kernel of size $O(k^2)$ (On the Kernelization of Global Constraints). Because its kernel does not depend on slack, it tests whether emission helps when the kernel stays small at every slack.
Baselines
The naive reference point is a plain lazy-clause-generation model with no special propagator: one clause per graph edge plus a linear sum over the cover variables. It shows what a general solver achieves on its own. Every method must clearly beat it on solved instances.
The strongest existing propagation method is the full VertexCover propagator of Propagation via Kernelization: The Vertex Cover Constraint, which combines crown kernelization with witness pruning. That paper reports that it visited "significantly fewer nodes… often by orders of magnitude" than decomposition or clique bounds, with the clearest gains on sparse SNAP graphs. No exact per-instance node count or runtime is reported in the material on Lacuna, so we will reimplement the method in the same host solver and re-measure it. Beating it means solving strictly more instances within the timeout on the same graphs. It also means achieving lower median time on instances both methods solve, while staying within a small constant factor on the dense DIMACS graphs where kernelization is known to struggle.
The strongest decomposition competitor is a static encoding solved by an industrial CP-SAT engine. That engine adds linear-relaxation bounds on top of clause learning. No reported result was found on Lacuna for CP-SAT on balanced vertex cover, so this baseline is measured fresh.
Two ablations isolate the key ingredient. The first is the explaining kernel propagator without emission, which gives reasons for prunings but never writes the kernel as clauses. The second is emission with naive explanations instead of minimal ones. A third control replaces the loss-less kernel with a standard lossy kernel and counts wrong answers. This confirms the soundness concern raised in On the Kernelization of Global Constraints rather than assuming it.
Fairness rules apply to all comparisons. Every method runs on identical instances, on a single thread, under the same timeout and memory cap. Every method also gets the same tuning budget, a small grid on a held-out tenth of the instances, which for our method covers $B$ and for CP-SAT covers its main search parameters.
Why not just…?
Why not just add explanations to the existing kernel propagator and stop there? This is the most serious threat. Explaining prunings already gives the learner nogoods, and that may capture most of the benefit. The argument for emission is that a pruning explanation records a single consequence. An emitted kernel encoding lets the solver derive new conflicts inside the core that the propagator never reported. Whether this matters is an empirical question. The explaining-only ablation measures it directly. If emission does not beat that ablation by a clear margin in solved instances on the sparse SNAP graphs, the conclusion of the project is that explanations suffice, and the emission machinery should be dropped.
Why not just encode everything statically and let CP-SAT's learning and linear relaxation do the work? For VERTEXCOVER a static encoding is polynomial: edge clauses plus a cardinality counter. The circuit-complexity barrier of Circuit Complexity and Decompositions of Global Constraints therefore does not rule it out the way it does for ALLDIFFERENT. What it lacks is the crown reasoning, which forces many vertices at once. Our method separates that reasoning from encoding size. For other NP-hard constraints, Explaining Propagators for String Edit Distance Constraints reports 227 of 250 median-string instances solved by a global propagator against 208 for the best integer-programming model. That is suggestive, not proof, for vertex cover. The CP-SAT baseline settles the question. If CP-SAT wins on SNAP, the hypothesis fails.
Why not just use a cheap polynomial bound or probing? For Boolean cover variables, bound and domain consistency coincide. The polynomial relaxation therefore takes the form of a clique-cover or linear bound, and the propagator of Propagation via Kernelization: The Vertex Cover Constraint already reports large node reductions over it. Probing every variable-value pair is described as prohibitively expensive in Reasoning about NP-complete Constraints. We include the clique bound inside the baselines and do not pursue probing further.
Proposed Experiments
The instances are the balanced vertex cover problems on DIMACS (dense) and SNAP (large, sparse) graphs used by Carbonnel and Hébrard. We regenerate cover budgets at several slack levels so that $z$ varies on purpose. EDGEDOMINATINGSET instances come from the same graphs.
The metrics are instances solved to optimality, PAR-2 time (mean runtime with each unsolved instance counted at twice the timeout), search nodes, and peak memory. We also record two diagnostics: explanation length, and the fraction of learned clauses that mention emitted kernel variables.
The decisive check has three conditions, and all three must hold for the claim to stand:
- Guarded emission solves more SNAP instances than both the explaining-only ablation and CP-SAT.
- The advantage shrinks or vanishes as slack grows, because the $(z+2)k$ bound inflates the kernel.
- On
EDGEDOMINATINGSET, whose kernel is slack-independent, the advantage persists at every slack level.
A further diagnostic tests the mechanism. Learned-clause reuse across sibling branches should rise when emission is on. If the gains appear without that rise, the explanation for the improvement is something other than the one proposed here.
References
- Propagation via Kernelization: The Vertex Cover Constraint
- On the Kernelization of Global Constraints
- Just-in-Time Hierarchical Constraint Decomposition
- Reasoning about NP-complete Constraints
- Circuit Complexity and Decompositions of Global Constraints
- Explaining Propagators for String Edit Distance Constraints