# Smaller Selection Networks for Cardinality Constraints Encoding

arXiv: https://arxiv.org/abs/1502.04551 · HTML: https://mlsanity.com/paper/1502.04551/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2015.

## Built on by (most cited first, 1 of 1)

- [Differentiable Top-k Classification Learning](https://mlsanity.com/paper/2206.07290/) (2022)

## Abstract (arXiv)

Selection comparator networks have been studied for many years. Recently, they have been successfully applied to encode cardinality constraints for SAT-solvers. To decrease the size of generated formula there is a need for constructions of selection networks that can be efficiently generated and produce networks of small sizes for the practical range of their two parameters: n - the number of inputs (boolean variables) and k - the number of selected items (a cardinality bound). In this paper we give and analyze a new construction of smaller selection networks that are based on the pairwise selection networks introduced by Codish and Zanon-Ivry. We prove also that standard encodings of cardinality constraints with selection networks preserve arc-consistency.