💻 computer science

Near-Optimal Encodings of Cardinality Constraints

This paper introduces novel, near-optimal CNF encodings for cardinality constraints that significantly reduce clause counts compared to previous methods, including a new encoding for AtMostOne that refutes a long-standing conjecture, establishes the first nontrivial unconditional lower bound for the problem, and improves upon a 50-year-old circuit complexity result, while also proposing a "grid compression" technique to achieve compact encodings for general AtMost $_k$ constraints.

Original authors: Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux

Published 2026-04-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are organizing a massive party with thousands of guests. You have a very strict rule: Only one person can be the "VIP" at any given time. If two people try to be the VIP simultaneously, the party crashes.

In the world of computer science, this rule is called an AtMostOne constraint. Computers need to translate this rule into a language they understand (called CNF, or a list of logical "clauses") so they can solve complex problems. The challenge? The more guests you have, the harder it is to write down the rules without creating a massive, unmanageable list of instructions.

This paper is about finding the most efficient way to write these rules. The authors, researchers from Carnegie Mellon University, have discovered new, smarter ways to write these instructions that are shorter, faster, and sometimes even break old records.

Here is a breakdown of their discoveries using simple analogies:

1. The Old Way vs. The New Way (AtMostOne)

The Problem:
Imagine you have 1,000 guests. The old, standard way to enforce the "One VIP only" rule was to write a note for every possible pair of guests saying, "You and you cannot both be VIP."

Result: For 1,000 guests, that's nearly 500,000 notes! It's a huge mess.

The Previous "Best" Solution:
A few years ago, a researcher named Chen invented a clever trick. He arranged the guests in a giant grid (like a spreadsheet) and used a "row/column" system. Instead of checking every pair, he just checked if a row was active and if a column was active.

Result: This reduced the notes from 500,000 down to about 2,000. It was considered the "perfect" solution for a long time.

The New Discovery:
The authors of this paper looked at Chen's grid and said, "What if we change the shape of the grid?"
Instead of a simple square grid (like a chessboard), they used a multi-layered web (a multipartite graph). Imagine the guests aren't just in rows and columns, but in a complex network of intersecting circles.

The Magic: By using this complex web, they managed to squeeze the number of notes down even further. They proved that Chen's "perfect" solution wasn't actually perfect. They found a way to write the rules with fewer notes than anyone thought possible.
The Bonus: This new structure also helped solve a 50-year-old puzzle in math about how to build the smallest possible electronic circuits for this specific type of logic.

2. The "Switch" Trick (Disjunctive Switching)

Now, imagine the rule is slightly different: "At most 5 people can be VIPs." (This is called AtMostk).

The Problem:
If you have 1,000 guests and allow 5 VIPs, the old methods required writing a massive number of rules, especially if 5 is a small number compared to 1,000. It was like trying to describe a specific path through a maze by listing every single dead end.

The New Trick: "Disjunctive Switching"
The authors introduced a concept they call Disjunctive Switching. Think of it like a traffic light system or a switchboard.

The Old Way: You write rules for every possible scenario. "If Person A is VIP, then B cannot be. If Person B is VIP, then A cannot be..." You write rules for every single branch of the "what if" tree.
The New Way: You install a master switch. You say, "The system will take one path." You write a rule that says, "Either Path A happens OR Path B happens." Then, you add a tiny rule that says, "If the switch is set to Path A, then Path B is automatically blocked."
Why it's cool: Instead of writing rules for every single branch (which is huge), you write one big "OR" rule and a few small "blocking" rules. It's like telling a delivery driver, "Go to the North side OR the South side," rather than writing a specific address for every single house on both sides. This saves a massive amount of space.

3. The "Grid Compression" (Shrinking the Map)

For the "AtMost 5 VIPs" problem, they also used a technique called Grid Compression.

The Analogy: Imagine you have a giant map of a city with 1,000 streets, but only 5 streets are currently "busy."
The Old Way: You try to monitor all 1,000 streets individually.
The New Way: You use a hash table (a smart filing system). You take the 1,000 streets and "compress" them onto a tiny, manageable map of only 50 spots. You have a rule that says, "If Street 100 is busy, it gets mapped to Spot 5 on the small map."
The Result: You only have to check the tiny 50-spot map to ensure you don't have too many busy streets. You've shrunk a massive problem into a tiny one without losing any accuracy.

Why Does This Matter?

You might ask, "Who cares if we save a few notes?"

Speed: Computers solving these problems (called SAT solvers) are used for everything from designing microchips to scheduling airline flights. If the instructions are shorter, the computer solves the problem faster.
Efficiency: The authors showed that their new methods, even though they are mathematically "imperfect" in some theoretical ways, actually work very well in the real world. They tested them on real computers, and in many cases, the new methods were faster than the old "perfect" methods.
Breaking Myths: For a long time, experts believed that to be fast, a computer's logic rules had to be "perfectly complete" (meaning the computer could instantly deduce every consequence). This paper showed that imperfect rules can sometimes be faster and more practical.

Summary

The authors took a fundamental problem in computer logic—how to tell a computer "don't let too many things happen at once"—and:

Redesigned the blueprint to use fewer instructions than ever before.
Invented a "switch" mechanism to avoid writing redundant rules.
Created a "compression" technique to shrink massive problems into tiny, manageable ones.

They proved that sometimes, the most efficient way to solve a problem isn't the most obvious one, and that a little bit of "messy" math can lead to much cleaner, faster computers.

1. Problem Statement

The paper addresses the problem of encoding cardinality constraints into Conjunctive Normal Form (CNF) for use in Boolean Satisfiability (SAT) solvers. Specifically, it focuses on two constraints:

AtMostOne ($AMO$): Asserts that at most one variable in a set $\{x_1, \dots, x_n\}$ is true.
AtMost $k$ ( $AM_k$ ): Asserts that at most $k$ variables in the set are true.

The goal is to minimize the number of clauses and auxiliary variables required for the encoding while maintaining desirable properties like propagation completeness (ensuring unit propagation derives all logical consequences). Prior to this work, the state-of-the-art for $AMO$ was Chen's product encoding ( $2n + 4\sqrt{n}$ clauses), and for $AM_k$ with small $k$ , encodings were generally of size $(k+1)n$ .

2. Methodology and Techniques

The authors introduce three novel theoretical frameworks and techniques to construct more compact encodings:

A. Graph-Theoretic Reinterpretation of Product Encoding

The authors reinterpret Chen's product encoding (traditionally viewed as a 2D grid) through the lens of graph theory.

Insight: Input variables are mapped to edges of a graph $G$ , and auxiliary variables correspond to vertices. An edge (input variable) being true implies its endpoints (auxiliary variables) are true.
Multipartite Graphs: Instead of a bipartite graph (grid), they utilize a complete multipartite graph with $\omega(1)$ parts. This increases edge density (edges per vertex), allowing for fewer auxiliary variables to represent $n$ edges.
Result: This leads to the Multipartite Encoding for $AMO$.

B. Disjunctive Switching

This is a new paradigm for encoding conditional logic ("switches") into CNF.

Problem: Naive encodings of algorithms with branches (e.g., "if condition A, enforce constraint X; else enforce constraint Y") sum the clauses of all branches, leading to redundancy.
Solution: The technique introduces wide clauses stating that some branch will be taken ( $x \to (c_1 \lor c_2 \lor \dots)$ ) and uses auxiliary variables to "turn off" the constraints of branches that are not taken.
Application: Applied to the Generalized Product Encoding for $AM_k$ , reducing the projection clauses from $(k+1)n$ to $2n$ .

C. Grid Compression

Inspired by hash table construction, this technique compresses a large grid of input variables into a smaller grid of auxiliary variables.

Mechanism: Input variables are arranged in a grid $M$ . The goal is to map "occupied" columns of $M$ to a smaller grid $L$ such that the constraint "at most $k$ columns in $L$ are occupied" implies the original constraint.
Combinatorics: The mapping relies on transversals (for the standard version) and cover-free families (for the disjunctive version) to ensure that distinct occupied columns in $M$ map to distinct columns in $L$ without collision, provided the number of true variables is $\le k$ .

3. Key Contributions and Results

A. Refuting Chen's Conjecture for AtMostOne

Theorem 1 (Multipartite Encoding): The authors present a propagation-complete encoding for $AMO$ using $2n + 2\sqrt{2n} + O(\sqrt[3]{n})$ clauses.
- This improves upon Chen's $2n + 4\sqrt{n}$ bound.
- It uses $\sqrt{2n}$ auxiliary variables.
- Significance: It refutes Chen's conjecture that his encoding was optimal. Notably, this encoding uses 3-CNF clauses (width 3), challenging the assumption that optimal $AMO$ encodings must be 2-CNF.

B. Circuit Complexity Implications

Theorem 6: The construction yields a smaller monotone boolean circuit for the threshold-2 function ( $T_2$ $T_{2}$ , the negation of $AMO$) with $2n + \sqrt{2n} + O(\sqrt[3]{n})$ gates.
- This improves a 50-year-old bound by Adleman.
- It resolves a 47-year-old open question by Bloniarz regarding the "single-level conjecture," proving that the smallest monotone circuits for $T_2$ are not single-level.

C. Unconditional Lower Bound

Theorem 2: The authors prove that any encoding of $AMO$ (even without assuming propagation completeness) requires at least $2n + \sqrt{n} + 1 - 2$ clauses for $n \ge 8$ $n \geq 8$ .
- This is the first nontrivial unconditional lower bound for this constraint.
- Combined with Theorem 1, it establishes that the optimal clause complexity for $AMO$ is $2n + \Theta(\sqrt{n})$ .

D. Improved Encodings for AtMost $k$

For $AM_k$ where $k$ is small relative to $n$ :

Theorem 3 (Grid Compression): An encoding using $4n + O(\sqrt[3]{kn^2})$ clauses for any $k = o(n)$ .
Theorem 4 (Disjunctive Grid Compression): An encoding using $2n + O(\sqrt{nk^3 \log^3_k n})$ clauses for $k = o(\sqrt[3]{n})$ $k = o (3 n)$ .
- For $k = o(\sqrt[3]{n})$ , this achieves $2n + o(n)$ clauses, significantly better than the previous best of $(k+1)n$ .
Theorem 7: By applying disjunctive switching to the generalized product encoding, they achieve $2n + O(k n^{k/(k+1)})$ clauses.

4. Empirical Evaluation

The authors conducted preliminary experiments to test the practical viability of their encodings, specifically the Disjunctive Grid Compression (DGC) encoding.

Findings:
- While the new encodings lack propagation completeness (a property often considered essential for performance), they performed competitively, and sometimes better, than standard encodings (like Sequential Counter) on specific benchmarks (Family L).
- On "pigeonhole-like" instances (Family M), propagation-complete encodings still outperformed the new methods, suggesting that propagation completeness remains crucial for hard, structured UNSAT instances.
Conclusion: The results challenge the folklore that propagation completeness is always necessary for high performance, suggesting a trade-off between encoding size and solver behavior depending on the instance type.

5. Significance

Theoretical Optimality: The paper closes the gap between upper and lower bounds for $AMO$ encodings, establishing the precise asymptotic complexity ( $2n + \Theta(\sqrt{n})$ ).
New Paradigms: It introduces Disjunctive Switching and Grid Compression as powerful general techniques for CNF encoding, which can likely be applied to other constraint types.
Circuit Complexity: It provides a breakthrough in monotone circuit complexity, disproving the single-level conjecture for the simplest quadratic boolean function.
Practical Impact: It demonstrates that theoretically optimal encodings (which are often larger in practice due to overhead) can be made smaller than previous "optimal" encodings, and that non-propagation-complete encodings can be practically useful, broadening the design space for SAT preprocessing.