Near-Optimal Encodings of Cardinality Constraints

Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux · 2026

Read Near-Optimal Encodings of Cardinality Constraints by Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux (2026) 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-2603-28954.txt.

Introduction

Krapivin, Przybocki, and Subercaseaux present new encodings for cardinality constraints that use fewer clauses. For the AtMostOne constraint, their CNF encoding beats the size of Chen's product encoding, which was thought optimal. The build also gives a smaller monotone circuit for the threshold-2 function, improving a 50 year old result. They prove a first nontrivial lower bound on clauses for the same constraint. For AtMost-k constraints, a grid compression technique yields encodings near 2n clauses for small k. The gains grow from new, broadly usable construction methods.

Catalog record

CREATORAndrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE107996
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.28954

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Near-Optimal Encodings of Cardinality Constraints Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux Abstract We present several novel encodings for cardinality constraints, which use fewer clauses than previous encodings and, more importantly, introduce new generally applicable techniques for constructing compact encodings. First, we present a CNF encoding for the 𝖠𝗍𝖬𝗈𝗌𝗍𝖮𝗇𝖾 ⁡ ( x 1 , … , x n ) \mathsf{AtMostOne}(x_{1},\dots,x_{n}) constraint using 2 ​ n + 2 ​ 2 ​ n + O ⁡ ( n 3 ) 2n+2\sqrt{2n}+O(\sqrt[3]{n}) clauses, thus refuting the conjectured optimality of Chen’s product encoding. Our construction also yields a smaller monotone circuit for the threshold-2 function, improving on a 50-year-old construction of Adleman and incidentally solving a long-standing open problem in circuit complexity. On the other hand, we show that any encoding for this constraint requires at least 2 ​ n + n + 1 − 2 2n+\sqrt{n+1}-2 clauses, which is the first nontrivial unconditional lower bound for this constraint and answers a question of Kučera, Savický, and Vorel. We then turn our attention to encodings of AtMost k ​ ( x 1 , … , x n ) \textsf{AtMost}_{k}(x_{1},\dots,x_{n}) , where we introduce grid compression , a technique inspired by hash tables, to give encodings using 2 ​ n + o ⁡ ( n ) 2n+o(n) clauses as long as k = o ⁡ ( n 3 ) k=o(\sqrt[3]{n}) and 4 ​ n + o ⁡ ( n ) 4n+o(n) clauses as long as k = o ⁡ ( n ) k=o(n) . Previously, the smallest known encodings were of size ( k + 1 ) ​ n + o ⁡ ( n ) (k+1)n+o(n) for k ≤ 5 k\leq 5 and 7 ​ n − o ⁡ ( n ) 7n-o(n) for k ≥ 6 k\geq 6 . 1 Introduction Cardinality constraints are a fundamental building block used to encode problems into conjunctive normal form (CNF). Due to their ubiquitous nature and importance to SAT solving, cardinality constraints have been extensively studied by the SAT community from both theoretical and experimental perspectives (see, e.g., [ 5 , 35 , 30 , 12 , 18 , 4 , 6 , 28 , 32 , 16 , 33 ] ). The most basic cardinality constraint is \mathsf{AtMostOne}(x_{1},\dots,x_{n}) , which asserts that at most one boolean variable x_{i} is true. While this constraint can be encoded using \binom{n}{2} clauses: \mathsf{AtMostOne}(x_{1},\dots,x_{n})\Longleftrightarrow\bigwedge_{1\leq i<j\leq n}(\overline{x_{i}}\lor\overline{x_{j}}), this quadratic blowup in the number of clauses is problematic when n is large. Fortunately, by introducing auxiliary variables, there are several encodings for \mathsf{AtMostOne}(x_{1},\dots,x_{n}) using only O(n) clauses, such as the sequential counter encoding from [ 35 ] . Empirically, SAT solvers perform much better when using linear encodings rather than the quadratic one [ 32 ] . Which cardinality constraint encoding is the most performant in practice depends on a number of factors, including the specific solver used and the encoding of the remaining constraints, but we focus on three factors that are amenable to theoretical analysis: the number of clauses in the encoding, the number of auxiliary variables, and whether the encoding is propagation complete (also known as arc consistent [ 19 ] ), a notion defined in Section 2 . Prior to the present work, the smallest known encoding for \mathsf{AtMostOne}(x_{1},\dots,x_{n}) was Chen’s product encoding [ 12 ] , which uses 2n+4\sqrt{n}+O(\sqrt[4]{n}) clauses and 2\sqrt{n}+O(\sqrt[4]{n}) auxiliary variables while also being propagation complete. Chen conjectured his encoding to be optimal with respect to the number of clauses. Our first contribution is to refute this conjecture: Theorem 1 (Multipartite Encoding) . There exists a propagation-complete encoding for the \mathsf{AtMostOne}(x_{1},\ldots,x_{n}) constraint using 2n+2\sqrt{2n}+O(\sqrt[3]{n}) clauses and \sqrt{2n}+O(\sqrt[3]{n}) auxiliary variables. Not only does our encoding improve upon the product encoding with respect to both the number of clauses and the number of auxiliary variables, but it also has a few conceptually interesting aspects. Perhaps surprisingly, our encoding includes an \textsf{AtMost}_{2} constraint within its definition, which makes it 3-CNF despite the fact that \mathsf{AtMostOne} is a 2-CNF function. While all previous linear encodings for this constraint in the literature are 2-CNF, Kučera, Savický, and Vorel [ 28 ] asked whether optimal propagation-complete encodings of \mathsf{AtMostOne} are 2-CNF; our result gives evidence to the contrary. Moreover, as we show in Section 3.4 , our construction yields a smaller monotone boolean circuit for the threshold-2 function, the negation of \mathsf{AtMostOne} , which improves on a 50-year-old construction of Adleman, 1 1 1 Adleman’s construction was first mentioned in print by Bloniarz [ 9 ] . answers a 47-year-old open question from Bloniarz [ 9 , p. 158] , and has implications for the so-called single-level conjecture [ 29 , 11 , 31 , 3 , 24 ] . Our encoding originates from reinterpreting Chen’s product encoding, traditionally presented in terms of a grid, as involving a complete bipartite graph. With this change of perspective, any graph with n edges can form the basis of an encoding of \mathsf{AtMostOne} , with 2n clauses that relate each edge to a pair of auxiliary variables corresponding to its endpoints and additional constraints depending on the graph structure. Our improvement in the second-order term comes from using a complete multipartite graph with \omega(1) parts, which has edge density 1 rather than 1/2 as in a complete bipartite graph; this allows for fewer vertices (i.e., auxiliary variables) for the same number of edges. With regard to lower bounds, Kučera, Savický, and Vorel [ 28 ] proved that every propagation-complete encoding of \mathsf{AtMostOne}(x_{1},\ldots,x_{n}) requires 2n+\sqrt{n}-2 clauses for n\geq 7 , so Theorem 1 is close to optimal. On the other hand, prior to the present work, no nontrivial lower bound was known without assuming propagation completeness. 2 2 2 Sinz [ 35 ] claimed that every encoding of \textsf{AtMost}_{k}(x_{1},\dots,x_{n}) has at least n clauses for all k\in[n-2] , but his proof has an irreparable gap. Indeed, the claim is false in general: Ben-Haim, Ivrii, Margalit, and Matsliah [ 6 ] showed that \textsf{AtMost}_{k}(x_{1},\dots,x_{n}) can be encoded using O(\log n) clauses when k=n-O(1) . Our second contribution provides such a bound—which is in fact better than the bound assuming propagation completeness—and answers a question from [ 28 ] : Theorem 2 . Every encoding of the \mathsf{AtMostOne}(x_{1},\ldots,x_{n}) constraint has at least 2n+\sqrt{n+1}-2 clauses for n\geq 8 . Together with Theorem 1 (or Chen’s result), this implies that the minimum number of clauses in an encoding of \mathsf{AtMostOne}(x_{1},\ldots,x_{n}) is 2n+\Theta(\sqrt{n}) . Next, we turn to the constraint \textsf{AtMost}_{k}(x_{1},\dots,x_{n}) , which asserts that at most k of the boolean variables x_{1},\dots,x_{n} are true. Sinz [ 35 ] gave an encoding for this using 7n-3\left\lfloor\log n\right\rfloor-6 clauses and 2n-2 auxiliary variables. When k is large relative to n , this is the smallest known encoding for \textsf{AtMost}_{k}(x_{1},\dots,x_{n}) as measured by the number of clauses. Our third contribution is to present smaller encodings when k is small relative to n : Theorem 3 (Grid Compression) . There is an encoding of the \textsf{AtMost}_{k}(x_{1},\dots,x_{n}) constraint using 4n+O\left(\sqrt[3]{kn^{2}}\right) clauses and O\left(\sqrt[3]{kn^{2}}\right) auxiliary variables. Theorem 4 (Disjunctive Grid Compression) . There is an encoding of the \textsf{AtMost}_{k}(x_{1},\dots,x_{n}) constraint using 2n+O\left(\sqrt{nk^{3}\log^{3}_{k}n}\right) clauses and O\left(\sqrt{nk^{3}\log^{3}_{k}n}\right) auxiliary variables. In particular, for k=o(n) , Theorem 3 gives an encoding using 4n+o(n) clauses and o(n) auxiliary variables; for

Read the complete text