# Solving Cyclic Antibandwidth Problem by SAT

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 41 references that are in the map.
- First posted on arXiv 5 Jan 2026.

## Builds on (most cited first, 3 of 3)

- [A New Look at BDDs for Pseudo-Boolean Constraints](https://mlsanity.com/paper/1401.5860/) (2014)
- [Effective Auxiliary Variables via Structured Reencoding](https://mlsanity.com/paper/2307.01904/) (2023)
- [A note on computational approaches for the antibandwidth problem](https://mlsanity.com/paper/1910.03367/) (2019)

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

- [Solving Minimum Span Antibandwidth and Cyclic Antibandwidth Labeling Problems](https://mlsanity.com/paper/2609.20091/) (2026)

## Abstract (arXiv)

The Cyclic Antibandwidth Problem (CABP), a variant of the Antibandwidth Problem, is an NP-hard graph labeling problem with numerous applications. Despite significant research efforts, existing state-of-the-art approaches for CABP are exclusively heuristic or metaheuristic in nature, and exact methods have been limited to restricted graph classes. In this paper, we present the first exact approach for the CABP on general graphs, based on SAT solving, called SAT-CAB. The proposed method is able to systematically explore the solution space and guarantee global optimality, overcoming the limitations of previously reported heuristic algorithms. This approach relies on a novel and efficient SAT encoding of CABP, in which the problem is transformed into a sequence of At-Most-One constraints. In particular, we introduce a compact representation of the At-Most-One constraints inherent to CABP, which significantly reduces the size of the resulting formulas and enables modern SAT solvers to effectively explore the solution space and to certify global optimality. Extensive computational experiments on standard benchmark instances show that the proposed method efficiently solves CABP instances of practical relevance, while identifying several previously unknown optimal solutions. Moreover, global optimal cyclic antibandwidth values are proven for a number of benchmark instances for the first time. Comparative results indicate that SAT-CAB consistently matches or surpasses the best-known solutions obtained by state-of-the-art heuristic algorithms such as MS-GVNS, HABC-CAB, and MACAB, as well as strong commercial Constraint Programming and Mixed Integer Programming solvers like CPLEX and Gurobi, particularly on general graphs, while also providing optimality guarantees. These results advance the state of the art for CABP and provide a new baseline for exact and hybrid methods on general graphs.